Решение задач 19 21 егэ по информатике с помощью python

Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 2023!

Сегодня разберём задачи из 19, 20 и 21 задания ЕГЭ по информатике. Для этих задач существует спасительный шаблон на Python, который позволяет получить на них правильные ответы и затратить минимум сил и времени.

Приступим к первой серии задач из демоверсии ЕГЭ по информатике 2021 года.

Задание 19 (Демо 2021)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат
две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один
ход игрок может добавить в одну из куч (по своему выбору) один камень
или увеличить количество камней в куче в два раза. Например, пусть
в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем
обозначать (10, 5). Тогда за один ход можно получить любую из четырёх
позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы,
у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах
становится не менее 77. Победителем считается игрок, сделавший
последний ход, т.е. первым получивший такую позицию, при которой
в кучах будет 77 или больше камней.

В начальный момент в первой куче было семь камней, во второй куче –
S камней; 1 ≤ S ≤ 69.

Будем говорить, что игрок имеет выигрышную стратегию, если он может
выиграть при любых ходах противника. Описать стратегию игрока – значит
описать, какой ход он должен сделать в любой ситуации, которая ему может
встретиться при различной игре противника. В описание выигрышной
стратегии не следует включать ходы играющего по этой стратегии игрока,
не являющиеся для него безусловно выигрышными, т.е. не являющиеся
выигрышными независимо от игры противника.

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

Решение:

Решим задачу с помощью шаблона на языке программирования Python. Если хотите ознакомится с аналитическим решением задач на теорию игр, можете посмотреть мои статьи по 19 Заданию, 20 Заданию, 21 Заданию. Но с помощью шаблонов на экзамене решать быстрее и легче.

Введём параметр p, который будет олицетворять позицию игры (ход).

def F(x, y, p):
    if x + y >= 77 and p==3: return True
    if x + y < 77 and p==3: return False

    return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1)
  

for s in range(1, 70):
    if F(s, 7, 1):
        print(s)

Заводим функцию F. Она принимает параметры: x — количество камней в одной куче, y — в другой, p-позиция игры.

Дальше описываем победу. Если x+y>=77 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.

Если, позиция уже равна 3, но сумарное количество камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).

Если мы не вышли на первых двух условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.

Т.к. здесь формулировка: «Известно, что Ваня выиграл своим первым ходом после неудачного первого
хода Пети.», то между функциями ставим союз ИЛИ (or).

В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи. Значение p всегда увеличиваем на 1.

Ответ: 18

Задание 20 (Демо 2021)

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

− Петя не может выиграть за один ход;

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

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

Решение:

Легко переделать из прошлой задачи.

def F(x, y, p):
    if x + y >= 77 and p==4: return True
    if x + y < 77 and p==4: return False
    if x + y >= 77: return False

    if p%2==0:
        return F(x+1, y, p+1) and F(x*2, y, p+1) and F(x, y+1, p+1) and F(x, y*2, p+1)
    else:
        return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1)
  

for s in range(1, 70):
    if F(s, 7, 1):
        print(s)

Теперь должен выигрывать Петя на своём втором ходе. Поэтому в условиях ставим позицию p=4.

Добавляется третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.

Здесь вопрос отличается от 19 задания. Здесь Петя должен побеждать при любом ходе соперника, а не при одном неудачном ходе Вани, поэтому добавляется ещё условие.

Для чётных p (это ходы Пети), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае.

Для нечётных p (это ходы Вани), возвращаем ходы через or.

Ответ:

Задание 21 (Демо 2021)

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

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

– у Вани нет стратегии, которая позволит ему гарантированно
выиграть первым ходом.

Решение:

Опять используем прошлый шаблон, но немного модернизируем.

def F(x, y, p):
    if x + y >= 77 and (p==3 or p==5): return True
    if x + y < 77 and p==5: return False
    if x + y >= 77: return False

    if p%2==1:
        return F(x+1, y, p+1) and F(x*2, y, p+1) and F(x, y+1, p+1) and  F(x, y*2, p+1)
    else:
         return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or  F(x, y*2, p+1)


def F1(x, y, p):
    if x + y >= 77 and p==3: return True
    if x + y < 77 and p==3: return False
    if x + y >= 77: return False

    if p%2==1:
        return F1(x+1, y, p+1) and F1(x*2, y, p+1) and F1(x, y+1, p+1) and  F1(x, y*2, p+1)
    else:
         return F1(x+1, y, p+1) or F1(x*2, y, p+1) or F1(x, y+1, p+1) or  F1(x, y*2, p+1)

for s in range(1, 70):
    if F(s, 7, 1):
        print(s)

print()

for s in range(1, 70):
    if F1(s, 7, 1):
        print(s)

Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).

Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.

В первой функции получилось 30,33, а во второй результатов нет. Получается ответ 30.

Ответ: 30

Следущая вариация задач отличается от первой лишь задачей в 19-ом задании. Рассмотрим демоверсию ЕГЭ по информатике 2022. Так же в этой серии задач будет одна куча, но из-за этого шаблон практически никак не меняется.

Задание 19 (Демо 2022)

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

Игра завершается в тот момент, когда количество камней в куче становится
не менее 29. Победителем считается игрок, сделавший последний ход,
т.е. первым получивший кучу, в которой будет 29 или больше камней.

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может
выиграть при любых ходах противника. Описать стратегию игрока – значит
описать, какой ход он должен сделать в любой ситуации, которая ему может
встретиться при различной игре противника. В описание выигрышной
стратегии не следует включать ходы играющего по этой стратегии игрока,
не являющиеся для него безусловно выигрышными, т.е. не являющиеся
выигрышными независимо от игры противника.

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

Решение:

Здесь вопрос отличается от прошлой 19-ой задачи. Здесь Петя должен выиграть в любом случае. Мы эту задачу можем воспринимать, как 20-ую из демоверсии 2021. Ведь там тоже игроку нужно обязательно было побеждать. Осталось написать шаблон с соответствующими параметрами.

def F(x, p):
    if x>=29 and p==3: return True
    if x<29 and p==3: return False
    if x>=29: return False

    if p%2==1:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
         return F(x+1, p+1) or F(x*2, p+1)

for s in range(1, 29):
    if F(s, 1):
        print(s)

Заводим функцию F. Т.к. у нас одна куча, то она принимает параметры: x — количество камней в куче, p-позиция игры.

Дальше описываем победу. Если x>=29 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.

Если, позиция уже равна 3, но камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).

Третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.

Если мы не вышли на первых трёх условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.

Для нечётных p (это ходы Вани), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае. При этом увеличиваем на 1 значение p.

Для чётных p (это ходы Пети), возвращаем ходы через or.

В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи.

Ответ: 14

Задание 20 (Демо 2022)

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

− Петя не может выиграть за один ход;

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

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

Решение:

Задача точно такая же, как и в 19 задании, только теперь обязательно должен побежать Петя на своём втором ходу (p=4), при любой игре Вани.

Пишем тот же шаблон, немного отредактировав его.

def F(x, p):
    if x>=29 and p==4: return True
    if x<29 and p==4: return False
    if x>=29: return False

    if p%2==0:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
         return F(x+1, p+1) or F(x*2, p+1)

for s in range(1, 29):
    if F(s, 1):
        print(s)

Получается 7 и 13.

Ответ:

Задание 21 (Демо 2022)

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

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

− у Вани нет стратегии, которая позволит ему гарантированно выиграть
первым ходом.

Если найдено несколько значений S, в ответе запишите минимальное из них.

Решение:

Опять используем прошлый шаблон, но немного модернизируем.

def F(x, p):
    if x>=29 and (p==3 or p==5): return True
    if x<29 and p==5: return False
    if x>=29: return False

    if p%2==1:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
         return F(x+1, p+1) or F(x*2, p+1)


def F1(x, p):
    if x>=29 and p==3: return True
    if x<29 and p==3: return False
    if x>=29: return False

    if p%2==1:
        return F1(x+1, p+1) and F1(x*2, p+1)
    else:
         return F1(x+1, p+1) or F1(x*2, p+1)

for s in range(1, 29):
    if F(s, 1):
        print(s)

print()

for s in range(1, 29):
    if F1(s, 1):
        print(s)

Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).

Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.

В первой функции получилось 12,14, а во второй 14. Получается ответ 12.

Ответ: 12

На сегодня всё. Мы рассмотрели самые распространённые вариации задач из 19-21 задания и подобрали к ним «противоядие». До новых встреч!

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

В задачах 19-21 ЕГЭ по информатике требуется проанализировать некую простую игру. Однако хотя игра и проста, её анализ может оказаться достаточно хитрым делом. Поэтому приходит мысль: а нельзя ли, чтобы этот анализ выполнил компьютер? (Спойлер: Можно!)

Немного теории.

Основную идею, лежащую в основе теории игр, подобных описанным в задачах ЕГЭ, можно выразить в двух словах: игроки умные. Это означает, что если у кого-то из игроков в текущей позиции есть возможность сделать выигрышный ход, то он этот ход сделает.

Таким образом, если в текущей позиции у игрока есть хотя бы один ход, ведущий к выигрышу, то это — выигрышная позиция для данного игрока. 

Если же в ответ на любой ход текущего игрока его противник выигрывает, то для текущего игрока такая ситуация — проигрышная.

Теперь более-менее понятно, как должна выглядеть программа, анализирующая ход игры. Прежде всего она должна проверить, не выиграл ли уже кто-то из игроков. Если это так — то дальнейший анализ позиции не требуется. 

Затем нужно просмотреть все возможные ходы текущего игрока. Если них есть хоть один выигрышный для него — в данной позиции он выиграл. Если же при любом его ходе выигрывает его противник — то можно считать, что данный игрок уже проиграл.

Если же неверно ни первое, ни второе — то ситуация неопределенная.(Вообще-то для игр из задач ЕГЭ всегда можно сказать, кто из игроков выиграет, такая неопределенность возникает только из-за ограничения на число ходов.)

Данную процедуру следует рекурсивно применять к позициям, возникающим по ходу игры.

А теперь — практика.

Решим программно задачи 19-21 из 8 варианта с сайта Полякова. Условие выглядит следующим образом:

(№ 3084) (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход
делает Петя. За один ход игрок может
  а) добавить в кучу один камень;
  б) увеличить количество камней в куче в два раза;
  в) увеличить количество камней в куче в три раза.
Игра
завершается в тот момент, когда количество камней в куче становится не
менее 43. Если при этом в куче оказалось не более 72 камней, то
победителем считается игрок, сделавший последний ход. В противном случае
победителем становится его противник. В начальный момент в куче было S
камней, 1≤S≤42.
Ответьте на следующие вопросы:
  Вопрос 1. Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
  Вопрос 2. Сколько существует значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите минимальное и максимальное значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.

Функция имеет три параметра: number (номер хода), limit (ограничение на количество ходов) и s (количество камней в куче). При первом обращении следует задавать значение number,  равное 1 (т.е. ходы мы нумеруем с единицы).

Переменная player принимает значение 1 для нечетных номеров ходов (т.е. ходы 1, 3 и т.д. совершает первый игрок) и значение 2 — для четных номеров. Переменная rival, наоборот, равна 2 для нечетных номеров ходов и 1 — для четных. Таким образом, player — это номер игрока, который делает текущий ход, а rival — номер его противника.

Прежде всего функция проверяет, не завершилась ли игра. Если число камней S не менее 43 и не более 72, то это означает, что текущий игрок проиграл: перед этим его противник сделал победный ход. Функция завершается, вернув значение rival. Если же число камней более 72, то соперник текущего игрока только что сделал проигрышный для себя ход, и выиграл текущий игрок. Программа возвращает значение player. 

Далее проверяется ограничение на число ходов. Если это ограничение превышено (number>limit), то дальнейшие ходы не выполняются и программа возвращает значение 0 (т.е. победитель не определён).

Далее осуществляются рекурсивные вызовы функции  hod с параметром number+1 (т.е. номер хода увеличен на единицу), с тем же самым значением limit и числом камней в куче 3S, 2S и S+1 (согласно условиям задачи).

Рекомендую сначала проверять значения, как можно сильнее отличающиеся от исходного (т.е. 3S и 2S) и потом S+1. Это позволяет уменьшить число вершин «дерева игры», которые анализирует программа. С этой же целью программа, обнаружив выигрышный для текущего игрока ход (т.е. результат вызова функции равен player), немедленно возвращает значение player и не выполняет дальнейших проверок ходов.

Если все три результата ходов равны rival, то в данной позиции все ходы текущего игрока приводят к его проигрышу, и программа возвращает значение rival. 

Если же для текущего игрока нет ни одного выигрышного хода, но у него есть ходы, не приводящие к его проигрышу, то ситуация неопределённая, и программа возвращает 0.

Теперь проведем анализ данной игры и получим ответы на заданные в задаче вопросы.

Первый вопрос: каково минимальное значение S, при котором второй игрок выигрывает своим первым ходом? Для ответа на него достаточно вызвать функцию для всех значений S таких, что 1<=S<=42, с ограничением на количество ходов, равным 2 (т.е. игроки делают по одному ходу). Если функция hod вернет значение, равное 2, то при данном начальном значении S второй игрок выигрывает в любом случае.

Второй вопрос: сколько имеется значений S, при которых первый игрок не может выиграть своим первым ходом, но гарантированно выигрывает вторым?

Для этого надо запустить программу два раза, первый раз с ограничением на число ходов 1, а второй раз — с ограничением 3. Если в первом случае программа вернет значение 0 (нет победителя), а второй — 1, то при данном S первый игрок не может гарантированно выиграть своим первым ходом, но непременно выигрывает вторым. Вместо ограничений 1 и 3 можно взять 2 и 4: дополнительный ход второго игрока (если он возможен) ничего не меняет.

Наконец, последний вопрос: при каких значениях S второй игрок не может гарантированно выиграть первым ходом, но обязательно выиграет вторым? Для этого надо опять запустить функцию дважды, с ограничением на число ходов 2 и 4. Если в первом случае функция вернет 0, а во втором — 2, то это искомое значение.   

Вот программа, которая выполняет данные проверки:

for s in range(1,43):
    h2 = hod(1,2,s)
    h4 = hod(1,4,s)
    rez = »
    if h2 == 2: rez = ‘*** 19 ***’
    if h2 == 0:
        if h4 == 1: rez = ‘*** 20 ***’
        if h4 == 2: rez = ‘*** 21 ***’
    print(s,h2, h4, rez)

Результат выполнения программы следующий (из него исключены строки, которые не дают ответов не поставленные вопросы):

7 0 1 *** 20 ***
12 0 2 *** 21 ***
13 0 1 *** 20 ***
14 2 2 *** 19 ***
39 0 2 *** 21 ***
40 0 1 *** 20 ***
41 2 2 *** 19 ***

Следовательно, ответы на вопросы задачи таковы:

Вопрос 1: такие значения — 14 и 41, минимальное — 14.

Вопрос 2: такие значения — 7, 13 и 40, всего их 3.

Вопрос 3: такие значения — 12 и 39. Минимальное — 12, а максимальное — 39.

А теперь решим задачи 19-21 из демонстрационного варианта ФИПИ 2022 г.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

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

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

Вопросы по сути те же, что и в задаче с сайта Полякова, однако правила игры другие. 

Перепишем функцию hod для данных правил:

Основная программа выглядит так же, как и в предыдущем случае. Единственное изменение — вместо range(1,43) в ней записано range(1,29).

Результат выполнения программы следующий (в нём опять-таки опущены несущественные строки):

Если Петя глуповат…

При составлении программы мы предполагали, что игроки — умные и ошибочных ходов не делают. Но на сайте «Решу ЕГЭ» очень часто встречаются задачи, где один из игроков дает маху. Вот пример задачи 19 (задача 27416):

Но как быть с тем, что наша функция предполагает безошибочную игру, а условие задачи подразумевает, что первый игрок сделал ошибочный ход? А очень просто: надо вызвать функцию четыре раза с позициями, которые могут получиться после первого хода Пети. В параметрах функции надо указать, что это — второй ход, и задать ограничение на количество ходов, равное двум. Если хотя бы в одном случае функция даст ответ, что выиграл второй игрок, то это и будет ответом на вопрос задачи.

Таким образом, основная программа выглядит так:

s1=7
for s2 in range(1,70):
    if hod(2,2,s1*2,s2)==2 or hod(2,2,s1,s2*2)==2 or hod(2,2,s1+1,s2)==2 or hod(2,2,s1,s2+1)==2:
        print(s2)
        break

Она дает правильный ответ: 18 камней.

Когда основная функция написана, не представляет сложности решить задачи 20 и 21. Вот их вопросы (правила игры, естественно, те же самые):

Основная программа опять-таки похожа на первый вариант, отличия незначительные:

s1=7
for s2 in range(1,70):
    h2 = hod(1,2,s1,s2)
    h4 = hod(1,4,s1,s2)
    rez = »
    if h2 == 0:
        if h4 == 1: rez = ‘*** 20 ***’
        if h4 == 2: rez = ‘*** 21 ***’
    print(s2,h2, h4, rez)

Результат работы программы (опять-таки опущены несущественные строки):

30 0 2 *** 21 ***
31 0 1 *** 20 ***
33 0 2 *** 21 ***
34 0 1 *** 20 ***

Таким образом, ответ на вопрос задачи 20 — это 31 и 34, а на вопрос задачи 21 — 30 (напомню, что там требуется минимальное значение из двух ответов: 30 и 33).

Итак, мы убедились, что задачи 19-21 ЕГЭ по информатике можно решить программно, и решение — не слишком сложное.

(c) Ю.Д.Красильников, 2021 г.

Введение

Привет друг! Проблемы с теорией игр? В этой статье мы разберем код, который решает любые прототипы стандартных 19-21 задач из КЕГЭ. Чтобы максимально понять ниже описанный код, я крайне рекомендую сначала научиться решать эти задачи ручками.

Условие

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в четыре раза.
В начальный момент в первой куче было 3 камня, во второй куче — S камней, 1 ≤ S ≤ 57. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 61. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 61 или больше камней.

1. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

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

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

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

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

Решение

Winpos

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

Обозначим переменные count1 и count2 как количество камней в 1 и 2 куче соответственно.
Если изначально суммарное количество камней в кучах меньше 61

if (count1 + count2 < 61)

и при любом следующем ходе оно становиться больше либо равно 61

((count1 + count2 + 1 >= 61) or
(count1 * 4 + count2 >= 61) or 
(count1 + count2 * 4 >= 61))

то мы возвращаем True, что означает что игрок находиться в выигрышной позиции.
Иначе мы возвращаем False, что означает что игрок не находиться в выигрышной позиции.

def winpos(count1, count2):
    if (count1 + count2 < 61) and ((count1 + count2 + 1 >= 61) or
       (count1 * 4 + count2 >= 61) or (count1 + count2 * 4 >= 61)):
        return True
    else:
        return False

Первая функция готова, приступим к написанию следующей.

Losspos

Теперь нам надо написать функцию, которая будет возвращать True если игрок находится в проигрышной позиции и False если игрок не находится в проигрышной позиции.

Если изначально игрок не находиться в выигрышной позиции

if not winpos(count1, count2)

и каждый следующий ход противника является выигрышным

(winpos(count1 + 1, count2) and winpos(count1, count2 + 1) and
 winpos(count1 * 4, count2) and winpos(count1, count2 * 4))

то мы возвращаем True, что означает что игрок находиться в проигрышной позиции.
Иначе, мы возвращаем False, что означает что игрок не находиться в проигрышной позиции.

def losspos(count1, count2):
    if not winpos(count1, count2) and (winpos(count1 + 1, count2) and
        winpos(count1, count2 + 1) and winpos(count1 * 4, count2) and
        winpos(count1, count2 * 4)):
        return True
    else:
        return False

Вторая функция готова, осталась еще одна.

Prewinpos

Последняя функция должна возвращать True если игрок находится в предвыигрышной позиции и False если игрок не находится в предвыигрышной позиции.

Если изначально игрок не находится в выигрышной позиции

if not winpos(count1, count2)

и любой следующий ход противника является проигрышным

(losspos(count1 + 1, count2) or losspos(count1, count2 + 1) or
 losspos(count1 * 4, count2) or losspos(count1, count2 * 4)):

то мы возвращаем True, что означает что игрок находится в предвыигрышной позциии.
Иначе, мы возвращаем False, что означает что игрок не находиться в предвыигрышной позциии.

def prewinpos(count1, count2):
    if not winpos(count1, count2) and (losspos(count1 + 1, count2) or
        losspos(count1, count2 + 1) or losspos(count1 * 4, count2) or
        losspos(count1, count2 * 4)):
        return True
    else:
        return False

Основа готова, осталось просто перебрать значения, чем мы сейчас и займемся.

1 Задача

Условие задачи можно воспринимать так: «Ваня находиться в выигрышной позиции(выигрывает за один ход)».

Изначально в первой куче 3 камня

count1 = 3

а во второй куче S камней, 1 ≤ S ≤ 57

for s in range(1, 58):

Перебираем все возможные комбинации с S, при которых игрок находится в выигрышной позиции

if winpos(count1 + 1, s) or winpos(count1, s + 1) or
   winpos(count1 * 4, s) or winpos(count1, s * 4):

и если хоть одна такая комбинация существует, то мы выводим S на экран и прерываем цикл.

print("19:", s)
break

Получается следующий код, который решает эту задачу

count1 = 3
for i in range(1, 58):
    if winpos(count1 + 1, i) or winpos(count1, i + 1) or
        winpos(count1 * 4, i) or winpos(count1, i * 4):
        print("19:", i)
        break

2 Задача

Условие задачи можно воспринимать так: «Ваня находится в проигрышной позиции».

Перебираем все возможные комбинации с S, при которых игрок находиться в проигрышной позиции, и если такие комбинации существуют, то мы выводим S на экран

for i in range(1, 58):
    if losspos(count1 + 1, i) or losspos(count1, i + 1) or
        losspos(count1 * 4, i) or losspos(count1, i * 4):
        print("20:", i)

3 Задача

Условие задачи можно воспринимать так: «Ваня находиться или в выигрышной или в предвыигрышной позиции»

Перебираем все возможные комбинации с S, при которых игрок находиться или в выигрышной или в предвыигрышной позиции, и если такие комбинации существуют, то мы выводим S на экран

if (winpos(count1 + 1, i) or predwinpos(count1 + 1, i)) and 
   (winpos(count1, i + 1) or predwinpos(count1, i + 1)) and 
   (winpos(count1 * 4, i) or predwinpos(count1 * 4, i)) and 
   (winpos(count1, i * 4) or predwinpos(count1, i * 4)):
   print("21:", i)

2 Способ

Подробней с этим методом решения теории игр вы можете ознакомится на канале Алексея Кабанова

Мемоизация

Для оптимизации рекурсии подключим декоратор cache из модуля functools.

from functools import cache

Moves

Напишем функцию moves, которая принимает количество камней в обеих кучах и возвращает всевозможные варианты ходов.

def moves(heap):
    a, b = heap
    return (a + 1, b), (a * 4, b), (a, b + 1), (a, b * 4)

Game

Напишем функцию game, которая рекурсивно описывает игру.

@cache
def game(heap):
    if sum(heap) >= 61:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    else:
        return max(steps) + 1

1-3 задача

Перебираем все значения s и выводим на экран необходимые данные.

for s in range(57, 0, -1):
    print(s, ": ", game((3, s)), " | ", [game(x) for x in moves((3, s))])

На выходе мы получаем полное дерево игры, в котором можно увидеть ответы на поставленные задачи.

1.

РЕШЕНИЕ ЗАДАНИЙ 19-21
ПРОГРАММИРОВАНИЕМ
суммарное время решения задач 19-21: 22 минуты

2.

ПОРЯДОК РЕШЕНИЯ
Если Вы собираетесь решать задания 19-21 через программирование, то есть 2
варианта:
• начинать решать не с 19-го задания, а с 20-го или с 21-го;
• решить 19-е задание на бумажке, 20 и 21 – через программу.
В любом случае полученные программой ответы нужно проверить вручную,
т.к. в программе нельзя задать условия вот такого типа:
• Петя не может выиграть за один ход, но может выиграть своим вторым
ходом независимо от того, как будет ходить Ваня;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть
первым ходом, но есть выигрышная стратегия, позволяющая ему выиграть
первым или вторым ходом при любой игре Пети.
И в том, и в другом случае программа выдаёт одинаковые числа (2 хода), т.е.
проверять возможность выигрыша за 1 ход нужно самостоятельно.

3.

О ПРОГРАММЕ
Есть несколько способов написать программу для решения задачи,
наиболее оптимальной по времени будет программа, решающая задачу
с помощью динамического программирования и сохраняющая
результаты в таблицу. В программе оба игрока не допускают ошибок
при игре, т.е. её можно использовать как для определения выигрышных
позиций как Вани, так и Пети.
Те места в программе, которые нужно будет менять в зависимости от
условий задачи, будут выделены жёлтым маркером. Всё остальное
остаётся неизменным (по крайней мере для решения задач 20-21).
Значения чисел в итоговой таблице:
Х – выигрыш Пети за Х ходов (например, 2 это выигрыш Пети за 2 хода);
-X – выигрыш Вани за Х ходов (например, -3 это выигрыш Вани за 3
хода).

4.

СТРУКТУРА ПРОГРАММЫ
1) создание таблицы, в которой будут храниться результаты игры;
2) рекурсивное заполнение таблицы с результатами (при этом
смысл чисел в таблице меняется: если в итоговом выводе число
5 означает победу Пети на 5 ходе, то при рекурсивном
заполнении таблицы число 5 в проверке будет означать
выигрыш Вани на 5 ходе, а не Пети);
3) вывод результатов (при этом никак не помечается, мог ли игрок
выиграть за меньшее количество ходов при другой игре
соперника: результаты нужно перепроверять вручную, в ответ
попадает самая длинная игра).

5.

ТИП 1: КОЛИЧЕСТВО
КАМНЕЙ В КУЧАХ
УВЕЛИЧИВАЕТСЯ

6.

1: УСЛОВИЕ
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает
Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два
раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок,
сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный
момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.
Задание 19.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая
ситуация возможна.
Задание 20.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

7.

1: СОЗДАНИЕ ТАБЛИЦЫ
19-е задание пропускаем, сначала решаем 20-е задание.
Код ниже создаёт таблицу из SUMMA*2 строк и SUMMA*2 колонок:
SUMMA = 77
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ]
SUMMA – сумма, при которой завершается игра.
Нумерация колонок и строк таблице начинается с 0.
Если в ячейке таблицы t[x][y] записано число 2, то это означает, что если в начале игры в первой куче
было Х камней, а во второй куче было У камней, то Петя гарантированно побеждает на 2 ходу.
Если в ячейке таблицы t[x][y] записано число -3, то это означает, что если в начале игры в первой куче
было Х камней, а во второй куче было У камней, то Ваня гарантированно побеждает на 3 ходу.
Таблица большая, т.к. разбираются все возможные ходы и есть ходы типа (1; 76) -> (1; 76*2)

8.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Перебираем все возможные сочетания из Х камней в первой куче и У
камней во второй куче. Сумма Х и У не может быть больше 76 (это конец
игры). Начинаем перебирать с конца:
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
….
Почему перебор начинается именно с конца, мы разбирать не будем:
это нужно для того, чтобы задачу можно было решить рекурсивно.
Изменять порядок перебора нельзя.

9.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Внутри цикла в отдельную переменную сохраним все возможные
ходы Пети:
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ]

10.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Если в таблице в t[x][y] стоит положительное число, это значит, что при таких Х и У Петя
побеждает. Но в нашем случае Х и У – это числа не ДО Петиного хода, это числа в ПОСЛЕ
Петиного хода, т.е. это начальные условия для Вани. Поэтому если в PetyaHod
оказывается положительное число, Петя не выигрывает, а, наоборот, проигрывает! Петя
будет выигрывать, если в PetyaHod оказалось отрицательное число. Нули тоже считаем
выигрышными для Пети (красивого объяснения здесь нет, это нужно, чтобы таблицу
можно было рекурсивно заполнить):
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ]
PetyaWin = [V for V in PetyaHod if V <= 0] # выбираем отрицательные числа из PetyaHod

11.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Программа ищет наиболее оптимальные стратегии и для Пети, и для Вани, поэтому если Петя
может выиграть, он будет стараться выиграть и сделать это за наименьшее количество ходов.
Это значит, что он возьмёт самое маленькое отрицательное число из Ваниного результата
(отрицательное – значит, Ваня проиграл, маленькое – значит, проиграл за маленькое число
ходов).
…. # продолжение программы с предыдущего слайда
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
Если Ваня проиграл за N ходов, то Петя выиграл за N + 1 ход, поэтому к ответу добавляем
единицу. Минус нам нужен, т.к. Ванин проигрыш (для Вани обозначается отрицательным
числом) это Петин выигрыш (для Пети обозначается положительным числом).

12.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Если Петя не может победить, значит, побеждает Ваня. Программа будет играть за Петю
наиболее оптимальным образом (т.е. Петя будет стараться максимально растянуть игру,
надеясь на ошибку противника). Если Ваня победил за N ходов, то Петя проиграл тоже за N
ходов, поэтому:
…. # продолжение программы
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
Берём максимальное положительное число из PetyaHod, т.к. Петя будет вести максимально
длинную игру при проигрыше, берём со знаком минус, т.к. при безошибочной игре Вани Петя
проигрывает.

13.

1: ВЫВОД ОТВЕТА
…. # продолжение программы
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == 2: # Петя победил на втором ходе
print(y) # выводим начальное количество камней во 2-й куче
Программа выводит всего 2 значения: 31 и 34. В условии просили найти два значения S, при
которых Петя выигрывает вторым своим ходом, но не может выиграть первым. Это значит,
что в данном случае значения 31 и 34 можно не перепроверять: других вариантов у нас всё
равно нет.
Ответ: 31 34

14.

1: ВСЯ ПРОГРАММА (20-Е ЗАДАНИЕ)
SUMMA = 77 # сумма, необходимая для выигрыша
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ]
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == 2: # Петя победил на втором ходе
print(y)

15.

1: РЕШЕНИЕ 21-ГО ЗАДАНИЯ
Т.к. программа играет оптимально и за Ваню, и за Петю, то чтобы найти значения S, при которых Ваня
выигрывает 2-м ходом, достаточно поменять условие в выводе:
…. # продолжение программы
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == -2: # Ваня победил на втором ходу
print(y) # выводим начальное количество камней во 2-й куче
Программа выводит числа 30 и 33. Минимальное число – 30, но нужно проверить, что в таком случае есть
какой-то Петин ход, позволяющий выиграть Ване за 1 ход.
Проверяем: (7, 30) -> (7, 60) -> (7, 120). Если Петя первым своим ходом умножит количество камней во 2-й куче
в 2 раза, Ваня выиграет за 1 ход. Значение 30 подходит в качестве ответа. Ответ: 30
Готовая программа находится на следующем слайде.

16.

1: РЕШЕНИЕ 21-ГО ЗАДАНИЯ
SUMMA = 77 # сумма, необходимая для выигрыша
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ]
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == -2: # Ваня победил на втором ходе (изменения только здесь)
print(y)

17.

1: РЕШЕНИЕ 19-ГО ЗАДАНИЯ
Программа для 20 и 21 задания не совсем подходит для решения 19-го задания, т.к. в
ней Петя должен играть с ошибкой. Чтобы найти ответ, программу можно немного
изменить: оставить таблицу t с правильными решениями и добавить таблицу d для
вычисления результатов при неправильном ходе Пети.
SUMMA = 77
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица ОПТИМАЛЬНОЙ игры Пети
d = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица для игры Пети с ошибкой

18.

1: РЕШЕНИЕ 19-ГО ЗАДАНИЯ
После заполнения таблицы t добавляем кусок кода, который заполняет таблицу d. В таблице d
Ваня должен выигрывать за 1 ход, а Петя должен проигрывать за 1 ход:
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ ДОПУСКАЕТ ОШИБКУ И ПРОИГРЫВАЕТ ЗА 1 ХОД
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ]
PetyaLose = [V for V in PetyaHod if V == 1] # Ваня выигрывает за 1 ход
if PetyaLose:
d[x][y] = -1 # Петя проигрывает за 1 ход
Остальные варианты нас просто не интересуют, поэтому мы их не заполняем.

19.

1: РЕШЕНИЕ 19-ГО ЗАДАНИЯ
Результат выводим, естественно, для таблицы d:
# ВЫВОД ОТВЕТА
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if d[x][y] == -1: # Ваня выигрывает за 1 ход после Петиной ошибки
print(y)
Вывод программы: числа 18, 19, 20, 21 … Минимальное число – 18. Ответ: 18
Готовая программа находится на следующем слайде.

20.

1: РЕШЕНИЕ 19-ГО ЗАДАНИЯ
SUMMA = 77
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица ОПТИМАЛЬНОЙ игры Пети
d = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица для игры Пети с ошибкой
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ НЕ ДОПУСКАЕТ ОШИБОК
for x in range(SUMMA-1, 0, -1):
# х — количество камней в первой куче
for y in range(SUMMA-x-1, 0, -1):
# y — количество камней во второй куче
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaWin = [c for c in PetyaHod if c <= 0]
if PetyaWin:
# если Петя может выиграть, он будет стараться выиграть
t[x][y] = -max(PetyaWin) + 1
else:
# если Петя проигрывает
t[x][y] = -max(PetyaHod)
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ ДОПУСКАЕТ ОШИБКУ И ПРОИГРЫВАЕТ ЗА 1 ХОД
for x in range(SUMMA-1, 0, -1):
# х — количество камней в первой куче
for y in range(SUMMA-x-1, 0, -1):
# y — количество камней во второй куче
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaLose = [V for V in PetyaHod if V == 1] # Ваня выигрывает за 1 ход
if PetyaLose:
# если Петя может проиграть Ване за 1 ход, он должен проиграть
d[x][y] = -1
# Петя проигрывает
# ВЫВОД ОТВЕТА
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if d[x][y] == -1: # Ваня выигрывает за 1 ход после Петиной ошибки
print(y, d[x][y])

21.

1: О ПОСТРОЕНИИ ТАБЛИЦЫ t
Если Вы запускаете программу в IDLE, то t у Вас сохраняется после первого решения
(20-го задания) и перестраивать t не нужно. Тогда при решении 21-го и 19-го заданий
t можно не строить заново. Т.е. если Вы уже решили 20-е задание, для решения 21-го
достаточно запустить только код для вывода ответа:
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == -2: # Ваня победил на втором ходе (изменения только здесь)
print(y)

22.

1: О ПОСТРОЕНИИ ТАБЛИЦЫ t
Программа для решения 19-го задания при построенной таблице t:
d = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица для игры Пети с ошибкой
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ ДОПУСКАЕТ ОШИБКУ И ПРОИГРЫВАЕТ ЗА 1 ХОД
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaLose = [V for V in PetyaHod if V == 1]
if PetyaLose:
d[x][y] = -1
# ВЫВОД ОТВЕТА
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if d[x][y] == -1: # Ваня

23.

1: ИТОГ
Даже если Вы не до конца понимаете отдельные участки кода (например, строчку
создания таблицы t), эти отдельные строчки всегда можно выучить. Смотрите сами,
что Вам проще: выучить наизусть несколько строчек кода (но написать их на экзамене
нужно будет без единой ошибки) или решить задачу математически.
Код программ для заданий 19-21 находится в курсе в файле «Пример 19-21.txt».

24.

ТИП 2: КОЛИЧЕСТВО
КАМНЕЙ В КУЧАХ
УМЕНЬШАЕТСЯ

25.

2: УСЛОВИЕ
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в
куче нечётно, остаётся на 1 камень больше, чем убирается). Игра завершается в тот момент, когда суммарное количество камней в кучах
становится не более 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет
40 или меньше камней. В начальный момент в первой куче было 20 камней, во второй куче — S камней, S > 20.
Задание 19.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите максимальное значение S, когда такая ситуация
возможна.
Задание 20.
Найдите три наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Задание 21
Найдите максимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

26.

2: ИЗМЕНЕНИЕ ПРОГРАММЫ ПОД 2-Й ТИП
Для того, чтобы рекурсивно заполнить таблицу при уменьшении количества камней в кучах, требуется:
1) определиться с максимальным размером таблицы (теперь мы сверху не ограничены)
2) понять, как запустить циклы в обратном порядке;
3) понять, как изменить формулы (в вычислении следующего хода).
Максимальный размер возьмём таким: SUMMA * 16. Такой размер таблицы позволяет вычислить игру
минимум в 4 хода.
SUMMA = 40
MAXS = 16*SUMMA
t = [ [0]*MAXS for i in range(MAXS) ]
Максимальный размер таблицы во всех задачах на уменьшение берём хотя бы 16*SUMMA.

27.

2: ИЗМЕНЕНИЕ ПРОГРАММЫ ПОД 2-Й ТИП
Запуск циклов в обратном порядке:
# СТРОИМ ТАБЛИЦУ ИГРЫ
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
…..
# ВЫВОД ОТВЕТА
x = 20
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
….
Если не очень понятно, почему нужно именно так запустить циклы, остаётся одно: зазубрить эти три
строчки кода.

28.

2: ИЗМЕНЕНИЕ ПРОГРАММЫ ПОД 2-Й ТИП
Теперь изменим формулы в PetyaHod.
Убрать камень из одной кучи легко:
PetyaHod = [ t[x-1][y], t[ ??? ][y], t[x][y-1], t[x][ ??? ] ]
Теперь уменьшим количество камней в куче в 2 раза, причём если камней – нечётное
количество, лишний камень заберём:
PetyaHod = [ t[x-1][y], t[ x//2 ][y], t[x][y-1], t[x][ y//2 ] ]
Но по условию ведь нам нельзя забирать лишний камень, он должен остаться в куче, поэтому:
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]

29.

2: ИЗМЕНЕНИЕ ПРОГРАММЫ ПОД 2-Й ТИП
Всё. Больше никаких изменений нет.
Программы для решения заданий 20, 21 и 19 на следующих
слайдах.

30.

2: ВСЯ ПРОГРАММА (20-Е ЗАДАНИЕ)
SUMMA = 40 # минимальное количество камней
MAXS = 16*SUMMA # берём хотя бы 16
t = [ [0]*MAXS for i in range(MAXS) ]
# СТРОИМ ТАБЛИЦУ БЕЗОШИБОЧНОЙ ИГРЫ
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
# ВЫВОД ОТВЕТА ДЛЯ 20-ГО ЗАДАНИЯ
x = 20
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
if t[x][y] == 2: # Петя выигрывает в 2 хода
print(y)
Программа выводит числа 42, 43, 61, 81, 82.
Вывод программы нужно перепроверить (что
Петя не может выиграть за 1 ход).
После перепроверки оказывается, что первые
три наименьших значения (42, 43, 61)
подходят.
Ответ: 42 43 61

31.

2: ВСЯ ПРОГРАММА (21-Е ЗАДАНИЕ)
SUMMA = 40 # минимальное количество камней
MAXS = 16*SUMMA # берём хотя бы 16
t = [ [0]*MAXS for i in range(MAXS) ]
# СТРОИМ ТАБЛИЦУ БЕЗОШИБОЧНОЙ ИГРЫ
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
# ВЫВОД ОТВЕТА ДЛЯ 21-ГО ЗАДАНИЯ
x = 20
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
if t[x][y] == -2: # Ваня выигрывает в 2 хода
print(y)
Программа выводит единственное число — 44.
Ничего перепроверять не будем, всё равно
других вариантов нет.
Ответ: 44

32.

2: ВСЯ ПРОГРАММА (19-Е ЗАДАНИЕ)
SUMMA = 40 # минимальное количество камней
MAXS = 16*SUMMA # берём хотя бы 16
t = [ [0]*MAXS for i in range(MAXS) ]
# СТРОИМ ТАБЛИЦУ БЕЗОШИБОЧНОЙ ИГРЫ
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
# РЕШЕНИЕ 19-ГО ЗАДАНИЯ
d = [ [0]*MAXS for i in range(MAXS) ]
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ ДОПУСКАЕТ ОШИБКУ И ПРОИГРЫВАЕТ ЗА 1 ХОД
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]
PetyaLose = [V for V in PetyaHod if V == 1]
if PetyaLose:
d[x][y] = -1
# ВЫВОД ОТВЕТА ДЛЯ 19-ГО ЗАДАНИЯ
x = 20
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
if d[x][y] == -1: # Ваня выигрывает за 1 ход после Петиной ошибки
print(y)
Программа выводит много чисел: 22, 23, 24 …
78, 79, 80. Максимальное — 80.
Ответ: 80