Тип 2
В двух предыдущих статьях мы научились решать 19-21 задания с одной кучей ручным и программным методами. Осознали базовую логику рекурсии и понимаем, как чередование ходов игроков сказывается на условии выбора верного ответа.
Пришло время усложнить задачу и перейти к играм с двумя кучами камней.
Сначала давайте вспомним, как выглядела игра с одной кучей. Состояние игры описывалось всего одним числом — количеством камней в этой куче. У игрока было 2-3 действия с камнями: убрать 1 камень, добавить 3, удвоить и так далее. Победа наступала при достижении определённого порога.
Теперь же состояние игры описывается двумя числами — количеством камней в первой и второй кучах. А главное изменение касается ходов: теперь игрок может менять состояние сразу двух куч, поочерёдно. То есть он может изменить количество камней как в одной куче, так и в другой.
Но помимо изменения вариантов ходов, в заданиях этого типа кроется еще одна загвоздка, которая значительно влияет на программное решение. Так, при решении заданий первого типа мы обходились всего одной основной функцией, которая могла выдавать ответы на все три задания.
Но здесь мы лишены такой роскоши: в 19 задании кроется одна формулировка, которая рушит привычный нам шаблон и заставляет добавлять еще одну функцию.
Как раз об этом мы и поговорим далее.
Алгоритм решения
Давайте первым делом рассмотрим типичную формулировку из ЕГЭ.
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза.
Игра завершается в тот момент, когда количество суммарное камней в кучах становится не менее 59.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 59 камней или больше.
В начальный момент в первой куче было 5 камней, во второй куче — S камней; 1 ≤ S ≤ 53.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.»
Заметили отличие? Нет, сейчас мы не про слова «две кучи камней» — это и так понятно.
Ключевое отличие здесь в том, что нам говорят: «Ваня выиграл своим первым ходом после неудачного хода Пети». То есть сразу сказано, что Петя облажался своим первым ходом. Что это означает?
Если вспомнить ручное решение заданий первого типа, то там мы говорили, что оппонент, в данном случае — Петя, всегда стремится сделать наименее ценный ход.
Напомним, что значат эти термины. При игре на увеличение камней в куче, мы называем наименее ценным ход, который меньше всего приближает к победе (±1, ±2 и т.п.). Именно этот ход будет делать проигрывающий игрок, чтобы максимально оттянуть своё поражение.
Наиболее ценный — это тот, который быстрее всего приближает к победе (умножение на 2, деление на 2, прибавление наибольшего числа и т.д.).
И вот в 19 задании сказано, что Пётр ошибся и вместо наименее ценного выбрал наиболее ценный ход. Конкретно в данном задании можно понять, что Петя взял, да и увеличил количество камней в 2 раза в одной из куч. Фатальная ошибка для него, и молниеносная победа для Ивана.
Это всё здорово, рассуждениями мы можем прийти к нужному ответу ручным методом. Но всё же мы здесь собрались, чтобы научиться решать такие задания кодом. А как такой факт отразится на коде?
До этого мы искали победителя вот таким условием:
Вспомним, что здесь происходит. Переменная h — это список результатов всех возможных ходов из текущей позиции. Каждый элемент списка говорит нам: «Если сделать этот ход, выиграет ли нужный игрок?»
Функция any возвращает истину, если хотя бы один элемент списка истинен. Мы используем её на своём ходу, потому что нам достаточно найти хотя бы один путь к победе. Если среди всех возможных ходов есть хоть один выигрышный — мы его и выберем, ведь мы играем оптимально.
Функция all возвращает истину, только если все элементы списка истинны. Мы применяем её на ходу противника, потому что противник тоже играет оптимально (для себя, не для нас). Он выберет лучший для себя ход, а значит, мы победим только в том случае, если любой его выбор ведёт к нашей победе.
Теперь вернёмся к девятнадцатому заданию. Там сказано, что Петя ошибся. Это значит, что он не выбирал оптимальный ход — он просто сделал какой-то ход, который оказался неудачным. Нам не нужно моделировать идеальную игру, нам нужно лишь проверить: существует ли вообще такая последовательность из двух ходов, при которой Ваня побеждает?
То есть нам нужна хоть какая-то любая последовательность двух ходов. Грубо говоря, здесь мы проверим, можно ли из начального числа камней в двух кучах за два умножения дойти до количества камней в 59 и больше.
Поэтому для 19 задания нам достаточно использовать только any на каждом шаге:
С этим разобрались, теперь напишем всю программу. Начнём с функции moves(), которая репрезентует возможные ходы игроков:
Как видите, здесь добавилась еще одна переменная. Теперь переменная a хранит в себе количество камней в первой куче, а переменная b — во второй. Таким образом, у каждого игрока есть четыре варианта ходов:
- Добавить камень в первую кучу: a + 1
- Удвоить количество камней в первой куче: a * 2
- Добавить камень во вторую кучу: b + 1
- Удвоить количество камней во второй куче: b * 2
Переходим к основной функции решения 19 задания. Первые два блока условий будут шаблонными:
Далее составляем список с результатами каждого хода:
И в конце нам нужно, чтобы хоть один ход из h привёл к победе, то есть нужно хотя бы одно истинное значение в этом списке:
Всё, можем перебирать возможное исходное количество камней во второй куче привычной нам записью:
Обратите внимание, что количество камней задано в условии: от 1 до 53 включительно. Значение переменной a также взято из условия: «в первой куче было 5 камней».
Вся программа пока что у нас выглядит так:
Запускаем ей и получаем число 14. Давайте убедимся в корректности нашего решения. Получается, что к началу игры в первой куче было 5 камней, а во второй — 14. Какой самый неудачный для себя ход мог совершить Петя?
Конечно, удвоить количество камней во второй куче! Получаем такие значения: 5 и 28, в сумме 33.
А Ваня, как победитель по жизни, просто удвоит количество камней в этой же куче и получит значения 5 и 56, что в сумме даёт выигрышное число 61, большее 59. Задача решена, ответ — 14.
Переходим к оставшимся двум. Их формулировки нам знакомы и не отличаются ничем от тех, что используются в первом типе заданий 20-21.
Воспользуемся описанным ранее шаблоном, разве что поменяем списочное включение для h:
В выражениях для перебора исходных значений также немного изменений. Меняются только сами функции: вместо двух аргументов, теперь передаём три:
Решение как для 19, так и для 20-21 заданий можно объединить в одну программу:
Запускаем её и получаем все три ответа на данные задания: 14; 24, 26 и 23, которые и запишем в ответы.
Пример 1
Рассмотрим еще одно задание с такой формулировкой:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 136.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 136 камней или больше.
В начальный момент в первой куче было 2 камня, во второй куче — S камней; 1 ≤ S ≤ 132.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.»
Выпишем все основные моменты:
- Победное количество камней 136
- В первой куче изначально 2 камня
- Ходы: +2 и *3
- Во второй куче может быть от 1 до 132 камней включительно
Осталось просто подставить эти числа в наш шаблонный код. Функция moves() будет выглядеть так:
Функция для решения 19 задания:
И для 20-21:
И перебор значений для ответа:
Собираем всё вместе:
Запускаем и видим на экране 4 числа: 15, 42, 43 и 41. Их и запишем в ответ на данное задание.
Пример 2
Для закрепления решим еще одно задание:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза.
Игра завершается в тот момент, когда количество суммарное камней в кучах становится не менее 123.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 123 камней или больше.
В начальный момент в первой куче было 9 камней, во второй куче — S камней; 1 ≤ S ≤ 113.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.»
Снова отметим ключевые моменты из задания:
- Победное количество камней 123
- В первой куче изначально 9 камней
- Ходы: +1 и *2
- Во второй куче может быть от 1 до 113 камней включительно
Сразу запишем весь код:
После его запуска перед нами будут ответы на данное задание: 29, 52, 56 и 51.
Итоги
Как вы могли заметить, все задания 19-21 вне зависимости от типа решаются шаблонными программами, в которых меняются некоторые числовые значения и операции.
Выведем теперь шаблонный код для решения 19-21 заданий второго типа:
Здесь следующие условные обозначения:
- *1 и *2 — возможные ходы (добавить два камня в первую кучу — a + 2, во вторую — b + 2 и т.п.);
- *3 — победное количество камней;
- *4 — максимальное количество камней во второй куче. Берётся из неравенства «1 ≤ S ≤ Х», где *4 = X + 1;
- *5 — исходное количество камней в первой куче.
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре.