Problem #32
Tags:
classical
loops
data-structures
c-1
c-0
implementation
Эта классическая задача пришла из тех древних времен, когда компьютеров вовсе не существовало.
Около 2000 лет назад была некая война, и в ходе одного из сражений защищающиеся оказались заблокированы нападавшими в пещере. Чтобы избежать плена, они решили встать в круг и убивать каждого третьего, пока не останется только один человек. Этот один по замыслу должен был покончить самоубийством - но он предпочёл сдаться и стать знаменитым историком. Задача как раз названа по его имени - более подробно вы можете прочесть о Задаче Иосифа (Флавия) в википедии.
А наша задача - для заданного числа человек N
и заданного шага K
- определить номер счастливчика который останется
последним в этой жеребьёвке. Например если всего 10 человек и выбывает каждый 3-й:
N = 10, K = 3
последовательность "вылета" будет такой (в скобках указаны выбывающие номера):
1-й круг: 1 2 (3) 4 5 (6) 7 8 (9) 10
2-й круг: 1 (2) 4 5 (7) 8 10
3-й круг: (1) 4 5 (8) 10
4-й круг: 4 (5) 10
5-й круг: 4 (10)
итак победителем оказался тот кто стоял четвертым в начальной позиции.
Входные данные содержат количество человек N
и размер шага K
.
Ответ должен содержать "выигрышный номер" (считая с 1).
Пример:
входные данные:
10 3
ответ:
4