Русская рулетка

Разберёмся с задачей сперва в случае чётного n. Очевидно, что при k = 1 ставить патрон нужно в крайнюю правую позицию, то есть, например, при n = 8 ответ будет выглядеть так:

.......X

Оценим вероятность застрелиться в этой ситуации. Напишем нули у тех слотов барабана, которые приведут нас к поражению, а у победных напишем единицы:

10101010

Отсюда понятно, что каждый следующий патрон нужно ставить так, чтобы не снижать вероятность собственной победы до тех пор, пока это возможно. Когда все слоты, ведущие к поражению, будут заполнены патронами, останется только получать лексикографически наименьший ответ с ростом k. Рассмотрим ответы для всех остальных k при n = 8:

.....X.X
...X.X.X
.X.X.X.X
.X.X.XXX
.X.XXXXX
.XXXXXXX
XXXXXXXX

В случае нечётного n рассуждения будут немного иными в начале, давайте построим ответ для n = 9 и k = 1:

........X
010101010

Можно поставить патрон аналогично чётному случаю, как описано выше. А можно поступить иначе — зарядить первый слот и сдвинуть барабан влево, смотрим:

X.......X => .......XX
010101010    101010100

Очевидно, что вероятность не изменилась, а ответ улучшился. Дальше придётся заряжать револьвер так, как описано для чётного случая:

.....X.XX
...X.X.XX
.X.X.X.XX
.X.X.XXXX
.X.XXXXXX
.XXXXXXXX
XXXXXXXXX

Разобравшись в принципе заполнения барабана патронами не должно составить труда научиться с помощью нескольких условий быстро отвечать на требуемые запросы.


Сложность алгоритма — O(p).