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

Задача . ДВ-2022


Задача

Темы:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) 1 камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней, такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (10, 6), (20, 10) и (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 223. В начальный момент в первой куче было 17 камней, во второй куче – S камней, 1 <= S <= 205.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
 
Вопрос 1
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. При каком минимальном значении S такое возможно?
 
Вопрос 2
Известно, что Петя имеет выигрышную стратегию. Укажите два значения при которых:
  • Петя не может победить первым ходом;
  • при любом ходе Вани Петя побеждает своим вторым ходом.
В ответе укажите два числа в порядке возрастания их значений.
 
Вопрос 3
Известно, что Ваня имеет выигрышную стратегию за один или два хода, при этом не имеет выигрышной стратегии в один ход. Найдите минимальное значение S, при котором это возможно.
 

Формат ввода ответов 

На каждое задание ответы пишите с новой строки. Если вы не знаете ответ на какое-либо задание, напишите в ответе любое число.

Например, если ответ на вопрос  1 - 1, на вопрос 2 - 2 и 3, на вопрос 3 - 4, то ответы надо записать так:

1
2 3
4


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

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