Решение через логические предикаты.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня либо увеличить количество камней в куче в пять раз. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 301. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 301 или более камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 300.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Задача 19. Укажите наименьшее значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задача 20. Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Задача 21. Найдите минимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Суть аналитического способа
Вместо того чтобы строить дерево игры и запускать рекурсию, мы формализуем условия каждой задачи в виде логических предикатов (функций, возвращающих True или False). Каждая функция отвечает на один вопрос: «может ли игрок гарантированно выиграть за определённое число ходов?»
Такой подход короче и меньше подвержен ошибкам с глубиной рекурсии. Весь код умещается в 4 функции и 4 цикла перебора.
Базовый предикат: победа за один ход
Начнём с самого простого – определения, можно ли выиграть сразу из позиции s.
Пояснение. Игрок побеждает за один ход, если после добавления 3 камней или после умножения на 5 количество камней станет не меньше 301. Оператор or означает, что достаточно хотя бы одного выигрышного хода.
Задача 19: позиция, где Петя обречён
Нам нужно найти такие S, при которых:
- Петя не может выиграть за один ход (not win1(s));
- Любой ход Пети (добавить 3 или умножить на 5) позволяет Ване выиграть за один ход (win1(s+3) и win1(s*5)).
Пояснение. Здесь используется and, потому что Петя – противник, он выберет худший для Вани ход. Поэтому Ваня должен быть готов к обоим вариантам. Если хотя бы один ход Пети не даёт Ване мгновенной победы – условие не выполнено.
Перебор и результат:
Задача 20: Петя выигрывает вторым ходом
Теперь Петя должен иметь возможность первым ходом перевести игру в позицию, где Ваня проигрывает (то есть в lose1).
Пояснение. Здесь используется or, потому что Пете достаточно одного выигрышного хода, чтобы попасть в проигрышную для Вани позицию.
Важно! Сама функция win2 не проверяет, что Петя не выигрывает за один ход. Это условие нужно добавить при переборе:
Ответ: два наименьших значения: 12 и 55.
Задача 21: Ваня выигрывает за 1–2 хода, но не гарантированно за 1
Самая сложная задача. Условия:
- При любом ходе Пети Ваня должен иметь возможность выиграть первым или вторым ходом.
- Но при этом Ваня не может гарантировать победу первым ходом (то есть хотя бы один ход Пети не даёт Ване мгновенной победы).
Формализуем:
- Если Петя делает ход +3, то Ваня должен выиграть за 1 ход (win1(s+3)) или за 2 хода (win2(s+3)).
- Если Петя делает ход *5, то Ваня должен выиграть за 1 ход (win1(s*5)) или за 2 хода (win2(s*5)).
- Но не может быть так, что оба хода Пети дают Ване мгновенную победу (win1(s+3) и win1(s*5) одновременно) – иначе у Вани была бы стратегия выиграть первым ходом.
В коде это реализовано через комбинацию условий:
Пояснение. В каждом слагаемом используется and, потому что для конкретного хода Пети мы проверяем комбинацию: один вариант даёт Ване победу за 1 ход, а другой – за 2 хода. Два слагаемых соединены or, потому что достаточно, чтобы хотя бы одна из двух ситуаций (когда Петя ходит +3 или *5) не давала Ване мгновенной победы.
Перебор и результат:
Ответ: минимальное S = 52.
Полный код для решения
Почему этот способ лучше
Аналитический подход короче и надёжнее рекурсивного. Вместо дерева ходов – цепочка логических условий. Вместо 30 строк на каждую задачу – 4 функции на все. Минимальный риск ошибиться с глубиной рекурсии или перепутать and/or. На экзамене это экономит время и силы.
Главный совет: сначала напишите win1 – это фундамент. Затем lose1, затем win2. И только потом lose2 для задачи 21. Такой порядок почти гарантирует, что вы не запутаетесь в логике.