19.07 Прочие прототипы

Аналитическое решение:

Эта задача легко сводится к куче камней. За один ход можно добавить к куче камня, ведь любое число, имеющее вид имеет лишь единицы, либо умножить количество камней в куче на . Тогда очевидно, что первым ходом Петя утроил количество камней, после чего Ваня сделал то же самое. Значит нам подойдёт значение

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

# Т.к. при решении мы оперируем количеством единиц в двоичной записи, то двоичное число 11001 - это
# то же самое, что и число 3 в обычной задаче на теорию чисел на кучи
# Если к числу слева и справа приписать его же, у нас запись утроится, и количество единиц станет
# в 3 раза больше, если к числу приписать число вида 2̂(2n) + 1, то количество единиц увеличится на 2
# ПРИМЕР - 2̂2 + 1 = 5, 5 = 10001, если приписать 10001 к записи, то получится на 2 единицы больше
# Или же 2̂3 + 1 = 9, 9 = 100001, аналогичная история, как и для числа 5.
# То есть, у таких чисел одна единица стоит в самом последнем разряде, а другая - в самом первом.

from functools import lru_cache


@lru_cache(None)
def f(a):
    if a >= 42:
        return 0
    moves = [f(a + 2), f(a * 3)]
    rick_win = [i for i in moves if i <= 0]
    if rick_win:
        return -max(rick_win) + 1
    return -max(moves)


for i in range(1, 42):
    if f(i + 2) == 1 or f(i * 3) == 1:
        print(i)
        break