Задача к ЕГЭ по информатике на тему «задачи под вебы» №83

Источник: https://kpolyakov.spb.ru/

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 12 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в круче становится не менее 51. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 51 или больше камней.

В начальный момент в куче было $S$ камней, $1 ≤ S ≤ 50$ .

1. При каких $S$ : 1a) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?

2. Назовите два значения $S$ , при которых Петя может выиграть своим вторым ходом?

3. Назовите значение $S$ , при котором Ваня выигрывает своим первым или вторым ходом.

В ответе укажите сначала левую границу отрезка из ответа на вопрос 1a), затем через пробел правую, затем через пробел ответ на вопрос 1б), затем через пробел первое значение из ответа на 2 вопрос, затем через пробел второе значение из ответа на вопрос 2, затем через пробел ответ на вопрос 3.

Из условия игроки могут делать ходы: $+1, 2, × 3$ .

1a. Найдем при каких значениях S Петя выиграет первым ходом: $S ∈ [17;50]$ . Эта позиция будет выигрышной для любого игрока, у которого она окажется.

1б. Для того чтобы Ваня выиграл своим первым ходом после хода Пети, у него должна быть позиция $[17;50]$ . При этом Петя не делает неудачные ходы. Это значение 16.

2. Для того чтобы найти начальные значения $S$ , из которых выигрывает Петя своим вторым ходом, нужно рассмотреть проигрышную позицию 16. Петя после своего первого хода должен сделать так, чтобы эти позиции достались Ване. Поэтому это значения $S = 14 и 15$ .

3. Найдем значение $S$ , при котором Ваня выиграет своим первым или вторым ходом. Для этого Ваня должен попасть в значения $S = 14,15$ либо в значения $[17;50]$ .

Получаем, что $S = 13$ , так как из него можно попасть в 39 ходом $× 3$ , в 14 ходом $+ 1$ или в 15 ходом $+ 2$ .

from functools import *
@lru_cache(None)
def f(a):
    if a >= 51: return 0
    n = [f(a+1), f(a+2), f(a*3)]
    t = [i for i in n if i <= 0]
    if t: return -max(t)+1
    return -max(n)
for i in range(1, 51):
    if f(i) == 1: print(i)

Ответ: 17 50 16 14 15 13