Задача Иосифа Флавия
Существует легенда, что Иосиф Флавий — известный историк первого века — выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из $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$.
Выходные данные
Выходной файл должен содержать единственное число — номер уцелевшего человека.
Тесты
| № | Ввод | Вывод |
| 1 | 10 3 | 4 |
| 2 | 500 100 | 480 |
| 3 | 50 10 | 36 |
| 4 | 1 1 | 1 |
| 5 | 41 3 | 31 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> using namespace std; int main() { int n, k, p; cin >> n >> k; int person = 0; for (int count = 2; count <= n; count++) person = (person + k) % count; cout << person+1; return 0; } |
Решение
Все люди в кругу пронумерованы от $0$ до $N-1$, началом будет person = 0 . Нужно исключить $person+(k-1)$ человека. Начальная позиция следующего раунда $person + k$. Но если номер исключенного человека $N-1$, следующая начальная позиция $N$, что выходит за пределы круга, по-этому мы берем остаток от деления на количество оставшихся в живых людей: (person + k) % count .
Таким образом круг уменьшается на одного человека, при этом номер уцелевшего в круге размера $N$ равняется номеру в получившемся круге размера $N-1$. Предполагаем, что это работает и в обратную сторону: берем круг размером count = 2, высчитываем, кто будет в начальной позиции в следующем раунде. count в таком случае количество не убитых, а живых, и оно увеличивается с каждым раундом до $N$. В конце прибавляем $1$, потому что в начале все значения были сдвинуты.