Условие:
Антон и Борис увлечены новой игрой, суть которой заключается в следующем. Один из игроков, по жребию, становится ведущим. Ведущий придумывает четырёхзначное слово (возможно, с нулями в старших разрядах) и передаёт ход другому игроку. В дальнейшем игроки делают ходы по очереди.
Выполняя ход, игрок может увеличить одну из цифр текущего числа на 1, 2 или 3. Естественно, новое значение этой цифры не должно превосходить девяти. Игрок, получивший в результате хода число 9999, проигрывает.
Определите, выиграет ли ведущий игрок при заданном начальном числе, если в процессе игры ни Антон, ни Борис не будут совершать ошибок.
Входные данные
В первой строке записано количество подтестов Q (3 ≤ Q ≤ 10). В каждой из последующих строк записано одно число в диапазоне от 1 до 9998 — очередное придуманное ведущим игроком число. Незначащие нули в этих числах не записываются.
Для 10 % тестов во всех их подтестах десятичная запись придуманных чисел содержит три девятки.
Выходные данные
Выведите строку из Q символов. В очередной позиции этой строки записывается символ 'Y', если ведущий игрок выигрывает, и 'N' — в противном случае.
Решить задачу на Python 3.8
Решение:
Для решения задачи о выигрыше ведущего игрока в игре с четырёхзначными числами, мы можем использовать подход, основанный на теории игр. Основная идея заключается в том, чтобы определить, в каких состояниях (числах) игроки находятся в выигрышной или проигрышной позиции.
Шаги решения:
1. Определение проигрышной позиции: Игрок, который получает число 9999, проигрывает. Это значит, что 9999 — это проигрышная позиция.
2. Определение выигрышной позиции: Если игрок может сделать ход, который приведет противника в проигрышную позицию, то текущее состояние является выигрышной позицией.
3. Анализ возможных ходов: Игрок может увеличить любую из четырёх цифр на 1, 2 или 3, при этом не превышая 9. Это означает, что для каждого числа мы можем проверить, какие числа могут быть достигнуты и являются ли они проигрышными.
4. Динамическое программирование: Мы можем использовать массив, где индекс будет представлять число, а значение будет указывать, является ли это число выигрышной (True) или проигрышной (False) позицией.
5. Заполнение массива: Начнем с 9999 (проигрышная позиция) и будем заполнять массив для всех чисел от 9998 до 0, проверяя, можно ли сделать ход в проигрышную позицию.
Реализация на Python:
- Мы создаем массив , который будет хранить информацию о том, является ли позиция выигрышной. - Заполняем массив, начиная с 9999 и двигаясь к 0, проверяя все возможные ходы. - Для каждого числа проверяем, можно ли сделать ход в проигрышную позицию. Если да, то текущая позиция считается выигрышной. - В конце выводим результаты для всех тестов. Таким образом, мы можем определить, выиграет ли ведущий игрок при заданном начальном числе.