Олимпиадный тренинг

Задача . 42868


Задача

Темы:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две карточки с двузначными числами. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может заменить одну карточку на карточку с меньшим значением по правилу – число, написанное на новой карточке, должно быть меньше заменяемого и формируется по правилу – старший разряд – одна из цифр заменяемого числа, младший разряд – одна из цифр второго числа. Например, пусть игра находится в позиции (25, 34), игрок может сделать из нее ход в одну из позиций (23, 34), (24, 34), (25, 32). Ход в позицию (25, 35) запрещен, так как 35 больше 34. Игра завершается в тот момент, когда игрок не может заменить ни одно из чисел. Победителем считается игрок, сделавший последний ход. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Известно, что Ваня выигрывает своим первым ходом независимо от игры Пети.
а) Определите максимальные числа, которые могут быть записаны на карточках в начале игры, в порядке возрастания.
б) Кто из игроков выигрывает при начале игры из позиции (23, 31)? В качестве ответа укажите два числа – число на первой карточке и число на второй карточке, которые получает выигрывающий игрок своим первым ходом.
в)  Для игры, описанной в задании а), определите, кто из игроков имеет выигрышную стратегию при игре из позиции (52, 31). Найдите позицию, в которую нужно прийти выигрывающему игроку первым ходом. Если таких позиций несколько, приведите вершину с максимальной суммой значений. В качестве ответа приведите два числа – сначала число, записанное на первой карточке, затем число, записанное на второй карточке.

Формат ответа: 
20 30
10 20
25 35

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя