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

(The Last Inch) КЕГЭ- 19-20-21. Модель решения

Игровая стратегия. Задания 19-20-21.
Задание из тренировочного варианта № 1

Рассмотрим программный подход к поиску ответа на 20 и 21 задание.
Ответ на задание 19 правильнее определить "руками" - минимальное S такое, что

(48-3) + (S-3) = 101 => S = 59

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

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

G - множество позиций, находящихся в игре. В данном случае, начально значение G = {(x,y) : x + y > 100}. Из множества G выделим подмножество St = {(48, y), y > 52} - позиции, для которых определяется ответ
L - множество позиций, при ходе из которых у игрока "нет выигрышной стратегии". В данном случае, начальное значение L = [ (x, y) : x + y <= 100] - это выигрышные позиции
W - множество позиций, при ходе из которых у играка "есть выигрышная стратегия". В данном случае, начальное значение есть пустое множество

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

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

def pi(pos) : # pi от слова периферия - окружение
  x, y = pos 
  return {(x - 3, y - 3), (x // 2 , y), (x, y // 2)} 
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 = 101 # параметр игры 
aa = 48 # определение стартовой строки 
St = set([(aa,i) for i in range(swin -aa , 16 * swin)]) 
G = set([(i,j) for i in range(aa+1) for j in range(swin - i, 16 * swin)]) # Множство стартовых точек
L = set([(i,j) for i in range(aa+1) for j in range(1, swin - i)]) # Множство точек для L
W = set() # Множство точек W
LW = {0 : set(), 1 : L} # словарь исходов 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
  R_St = R & St # значения для анализа
  LW[(t + 1) % 2] = LW[(t + 1) % 2].union(R) # перенос результатов в финальные множества 
  print('t ={}, min(R&St) ={}, max(R&St) ={} '.format(t,min(R_St),max(R_St))) # вывод результатов

Ответ на задание 20 найдем в строке t=3
Ответ на задание 21 найдем в строке t=4

Код программы Step можно запомнить.
Для двух куч с уменьшением надо понять, какие ограничения ввести для x, y при заполнении G - выбрали 8swin, так как рассмотриваем только 4 такта (2222 = 16)
Можно сделать более общие задания множеств (более простые), хотя это сильно увеличит время (в примере ограничиличь 8 вместо 16)

def pi(pos) : # pi от слова периферия - окружение
  x, y = pos 
  return {(x - 3, y - 3), (x // 2 , y), (x, y // 2)} 
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 = 101 # параметр игры 
aa = 48 # определение стартовой строки 
St = set([(aa,i) for i in range(swin -aa , 8 * swin)]) 
L = set([(i,j) for i in range(swin) for j in range(swin - i)]) # Множство точек для L (x + y < 101)
G = set([(i,j) for i in range(8 * swin) for j in range(8 * swin)]) # Множство всех точек (x < 808,  y< 808) 
G = G - L # убираем финальные
W = set() # Множство точек W
LW = {0 : set(), 1 : L} # словарь исходов 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
  R_St = R & St # значения для анализа
  LW[(t + 1) % 2] = LW[(t + 1) % 2].union(R) # перенос результатов в финальные множества 
  print('t ={}, min(R&St) ={}, max(R&St) ={} '.format(t,min(R_St),max(R_St))) # вывод результатов

Печать

(The Last Inch) КЕГЭ- 19-20-21. Модель решения

(48-3) + (S-3) = 101 => S = 59

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

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

L - множество позиций, при ходе из которых у игрока "нет выигрышной стратегии". В данном случае, начальное значение L = [ (x, y) : x + y <= 100] - это выигрышные позиции

W - множество позиций, при ходе из которых у играка "есть выигрышная стратегия". В данном случае, начальное значение есть пустое множество

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

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