Статья Автор: Лебедев Дмитрий Алексеевич

Задание с одной кучей

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

– добавить в кучу 1 камень;
– добавить в кучу 5 камней;
– увеличить количество камней в куче в 3 раза.

Например, из кучи 20 камней за один ход можно получить кучу из 21, 25 или 60 камней.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 124. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 124 или больше камней. В начальный момент времени в куче было S камней, 1≤S≤123.

19. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
20, 

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

21, 

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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


Рассмотрим программный способ решения
  1. Создаем  множества/словари 
    G - множество точек в игре  = [p for p in range(1,egame)] (egame = 124
    W - множество точек, при ходе из которых есть ВС (выигрышная стратегия) (W = set())
    L - множество точек при ходе из которых ВС переходит к противнику ( L = set('V', ) V -  все позиции Победы/окончания игры)
    Rez - словарь для записи промежуточных результатов
  2. Рассматриваем игру как "такты" - нечётные ход Пети, чётные - ход Вани
    Нас интересуют только 4 такта, но будем играть пока G "не станет пустым"
    На каждом ходе/такте перебираем все элементы G и определям, чем они являются для игрока (появление - проподание ВС)
    Игру  рассматриваем от Пети и он должен пойти в L (получить ВС), если все ходы ведут в W - то он передает ВС Ване (эти поля становятся победными для Вани)
  3. Для работы будем использовать пару подпрограмм:
    - def pi(pos) - возвращает множество возможных позиций хода Это индивидуальная программа
    - def shag(G, t) - стандартная программа, которая в зависимости от четности такта (чей ход) проверяет все игровые позиции на наличие ВС у игрока. Возвращает множество отобранных позиций 
  4. Основной блок: Пока G не пусто:
    - получаем множество отобранных позиций R, записываем в результат или выводим на экран
    - добавляем R в W или L, вычиьаем их G
  5. Анализ (визуальный) результатов и получение ответа 

Печать