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

Zagotovka КЕГЭ- 19-20-21. Модель решения на одну кучу

Модель решения можно представить так:

Определям три множества:

G - множество позиций, находящихся в игре.
L - множество позиций, при ходе из которых у игрока "нет выигрышной стратегии". В начале в L заносятся позиции, "объявленные победными". L - множество позиций, в которые надо стремиться попасть.
W - множество позиций, при ходе из которых у играка "есть выигрышная стратегия". В начале в W заносятся позиции, "объявленные проигрышными" (обычно это пустое множество). W - множество позиций, которые надо избегать. Как правило,

Для решения определим пару программ:

Pi - определяющую позиции, в которые можно попасть из текущей
Step - определяющую результат заданного такта. Такт - это ход одного из игроков. Первый игрок (Петя) делает ходы на нечетных тактах (1, 3, 5, ...), а второй (Вася) на чётных (2, 4, 6, ...)

Решение задания состоит в "настройке" множеств G, L, W, программы Pi и "стартового" множества (для двух куч)
Ниже приведен шаблон для решения заданий с одной кучей и несколько примеров "настройки

def pi(pos) : # pi от слова периферия - окружение
  return # здесь множество позиций в которые есть переход 
def step (S, X, t): # поиск результата такта t
  Y = set() # результат работы
  for pos in S : # перебор игровых точек и поиск результата в зависимости от такта работы
    if (t % 2 == 1) and (pi(pos) & X)  or  (t % 2 == 0) and (pi(pos) <= X): Y.add(pos) 
  return Y 
swin = int(input()) # параметры игры
G = set([i for i in range(swin, swin * 3 ** 4)]) # Множство стартовых точек
LW = {0 : set([i for i in range (0, swin, 2)]), 1 : set([i for i in range (1, swin, 2)])} # словарь исходов L = LW[0], W = LW[1]
t = 0 # инициализация такта
while t < 6: # просмотр 6 тактов работы
  t +=1 # переход к новому такту
  R = step(G, LW[t % 2], t) # получение результата работы
  G = G - R #  уменьшение множества G
  LW[(t + 1) % 2] = LW[(t + 1) % 2].union(R) # перенос результатов в финальные множества 
  print('R{} = '.format(t),sorted(R),) # вывод результатов

Печать

Zagotovka КЕГЭ- 19-20-21. Модель решения на одну кучу

Модель решения можно представить так:

Определям три множества:

G - множество позиций, находящихся в игре.

Для решения определим пару программ:

Pi - определяющую позиции, в которые можно попасть из текущей