eolymp
bolt
Try our new interface for solving problems
Məsələlər

Задача Иосифа Флавия

Задача Иосифа Флавия

Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из \textbf{41} иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю. В нашем варианте мы начнем с того, что выстроим в круг \textbf{N} человек, пронумерованных числами от \textbf{1} до \textbf{N}, и будем исключать каждого \textbf{k}-ого до тех пор, пока не уцелеет только один человек. (Например, если \textbf{N=10}, \textbf{k=3}, то сначала умрет \textbf{3}-й, потом \textbf{6}-й, затем \textbf{9}-й, затем \textbf{2}-й, затем \textbf{7}-й, потом \textbf{1}-й, потом \textbf{8}-й, за ним - \textbf{5}-й, и потом \textbf{10}-й. Таким образом, уцелеет \textbf{4}-й.) \InputFile Во входном файле даны натуральные числа \textbf{N} и \textbf{k}. \textbf{1} ≤ \textbf{N} ≤ \textbf{500}, \textbf{1} ≤ \textbf{k} ≤ \textbf{100}. \OutputFile Выходной файл должен содержать единственное число - номер уцелевшего человека.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
10 3
Çıxış verilənləri #1
4