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

Разбор задания 19-20-21 из варианта Статграда (2024.10.24)

Задания 19-21 (ссылка на задание)

Правила игры:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может выполнить любое из следующих трёх действий: 1) убрать из кучи один камень; 2) если количество камней в куче кратно трём, уменьшить его в три раза, в противном случае убрать из кучи два камня; 3) если количество камней в куче кратно пяти, уменьшить его в пять раз, в противном случае убрать из кучи три камня.
Например, если в куче 12 камней, то за один ход можно получить 11, 4 или 9 камней.
Игра завершается, когда количество камней в куче становится не более 19.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 19 или меньше камней.
В начале игры в куче было S камней, S > 19.

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

Приведен "стандартный" код решения. Поясним порядок его получения и поиск ответов

Поясним ход решения и процесс написания программы

Создаем и отлаживаем подпрограмму def pi(pos). Это подпрограмма возвращаетмножество значений ("Образ"),
в которые можно попасть из позиции pos.
Проверяем работу для значений pos кратных/не кратных 3 и 5
Определяем переменную swin, которая определяет условие окончания игры (для этого варианта swin=19
(делаем её вводимой, для возможности посмотреть процесс)
Определяем множество "стартовых позиций" St - по условию оно неограничено, но вопросы касаются только 4 "тактов",
значить "максимальное движение/уменьшение" равно 5*5*5*5 =625 (на практике можно брать значительно меньше)
Пишем процедуру def step0(S), возвращающую множество значений (W1), для которых у Пети есть "выигрышная стратегия"(ВС) в один ход.
Для этого "пробегаем" значении множества S и проверяем, что не все точки "образа" лежат внутри множества S
Запускаем W1=step0(St), определяем "оставшиеся" позиции (St=St-W1) и можем, для вывести размеры множеств W1, St (для понимания, что происходит)
Используя "copy-paste" создаем программу step1(S,X), которая "отбирает" в множестве S все точки, "образ" которых лежит в множестве X.
Запуск L1=step1(St,W1) позволит получить ответ на задание 19, так как множество L1 будет множеством позиций, для которых выигрышная стратегия в один ход есть у Вани. Выводим L1 в "удобном" порядке. Определяем "оставшиеся" позиции (St=St-L1)
Используя "copy-paste" создаем программу step2(S,X), которая "отбирает" в множестве S все точки, "образ" которых имеет не пустое пресечение с множеством X.
Запуск W2=step2(St,L1) позволит получить ответ на задание 20, так как множество W2 будет множеством позиций, для которых выигрышная стратегия в два хода есть у Пети. Выводим W2 в "удобном" порядке. Определяем "оставшиеся" позиции (St=St-W2)
Для дальнейшего решения не надо создавать новых программ.
Запуск L2 = step1(St,W1.union(W2)) позволит получить ответ на задание 21, так как множество L2 будет множеством позиций, для которых выигрышная стратегия в неболее чем два хода есть у Вани. Выводим L2 в "удобном" порядке.

Полученный код (более 30 строк) может показаться "большим", но "простота" его написания ("copy-paste") и "универсальность" позволяют использовать данный код на экзамене
Код программы приведен в "упрощенном" виде (без лишних переносов, комментариев - как на экзамене)

def pi (x):
  a = {x-1}
  if x % 3 == 0 : a.add(x // 3) 
  else : a.add(x - 2)
  if x % 5 == 0 : a.add(x // 5) 
  else :  a.add(x - 3)
  return a

def step0(S):
  Y = set()
  for d in S:
    if not (pi(d).issubset(S)): Y.add(d)
  return Y

def step1(S,X):
  Y = set()
  for d in S:
    if pi(d).issubset(X): Y.add(d)
  return Y

def step2(S,X):
  Y = set()
  for d in S:
    if pi(d) & X: Y.add(d)
  return Y

swin = int(input())
St = set(i for i in range(swin + 1, swin * 625))
W1 = step0(St)
St = St - W1
L1 = step1 (St,W1)
print('*19*',sorted(L1))
St = St - L1
W2 = step2 (St,L1)
print('*20*',sorted(W2)[:10])
St = St - W2
L2 = step1 (St,W1.union(W2))
print('*21*',sorted(L2))

Чтобы оставить комментарий нужна авторизация

Печать