Josephus Problem

Problem #32

Tags: classical loops data-structures

Who solved this?

Back to English version

Эта классическая задача пришла из тех древних времен, когда компьютеров вовсе не существовало.

Около 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
You need to login to get test data and submit solution.