19.01 Перекладывание камней одна куча

Решение руками

Максимальный ход доступный нам в партии это . Определим отрезок, в котором игра заканчивается за один ход. Минимальное значение отрезка равняется: (округляем в большую сторону) =

Получается, что в отрезке [14;39] игра заканчивается в один ход. Если значение S после первого хода Пети не находится в данном отрезке, то Ваня специально совершит такой ход, чтобы после него значение S находилось в данном отрезке для того чтобы Петя смог завершить партию следующим ходом. А если значение S после первого хода уже находится в данном отрезке, то Ваня специально совершить такой ход, чтобы не завершить партию, а просто передать очередь хода Пете для того чтобы он завершил партию. Распишем значения и стратегии, при которых Петя не может победить за один ход, но может победить вторым ходом после неудачного хода Вани:

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

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

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

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

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

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

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

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

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

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

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

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

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

В ответ нужно указать количество значений S. Ответ:

Программное решение

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 40: # если камней в куче стало больше 39
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+6),game(first_heap*3)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)
count = 0
for i in range(1,40):
    # проверка, что Петя не может выиграть за один ход
    # проверка, что Петя может выиграть вторым ходом после неудачного хода Вани. Расписываем всевозможные первые два хода и проверяем можно ли после них завершить игру за один ход.
    if game(i) != 1 and (game(i+1+1) == 1 or game(i+1+6) == 1 or game(i+1*3) == 1 or game(i+6+1) == 1 or game(i+6+6) == 1 or game(i+6*3) == 1 or game(i*3+1) == 1 or game(i*3+6) == 1 or game(i*3*3) == 1):
        count += 1
print(count)