|
Задача Иосифа Флавия
(Время: 1 сек. Память: 16 Мб Сложность: 29%)
Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю…
В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только один человек.
Например, если N=10, K=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.
Требуется написать программу, которая по заданным N и K будет определять номер уцелевшего человека.
Входные данные
Входной файл INPUT.TXT содержит два натуральных числа N и K. Ограничения: N ≤ 500, K ≤ 100.
Выходные данные
В выходной файл OUTPUT.TXT нужно вывести номер уцелевшего человека.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10 3 | 4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
