e-olymp 971. Задача Иосифа Флавия

Задача

Существует легенда, что Иосиф Флавий — известный историк первого века — выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.

В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от $1$ до $N$, и будем исключать каждого $k$-ого до тех пор, пока не уцелеет только один человек. (Например, если $N=10$, $k=3$, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним — 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)

Входные данные

Во входном файле даны натуральные числа $N$ и $k$. $1 ≤ N ≤ 500, 1 ≤ k ≤ 100$.

Выходные данные

Выходной файл должен содержать единственное число — номер уцелевшего человека.

Тесты

Входные данные Выходные данные
10 3 4
17 5 11
76 32 58

Код решения

Решение задачи

Все делается по алгоритму: убирается каждый $k$-тый человек до тех пор, пока не останется один.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *