Задание 21 из ЕГЭ по информатике: задача 1

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

1. Прибавить к одной (любой) куче два камня.

2. Увеличить количество камней в одной (любой) куче в два раза.

Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (10; 7), (7; 7), (5, 9) и (5, 14).

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

Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.

В первой куче было 7 камней, а во второй S (1 <= S <= 100). Найдите минимальное значение S, при котором одновременно выполняются два условия:

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

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