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

Задача . 192021-11-20


Задача

Темы:
Два  игрока, Петя  и  Ваня,  играют  в  следующую  игру.  Перед  игроками  лежит куча  камней.  Игроки  ходят  по  очереди,  первый  ход  делает  Петя.  За один  ход игрок  может добавить в  кучу один  камень,  добавить  два  камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который  этот  же  игрок  делал  на  предыдущем  ходу.  Повторять  чужие  ходы  и свои более старые ходы разрешается. Например,  если  в  начале  игры  в  куче  3  камня,  Петя  может  первым  ходом получить  кучу  из  4,  5  или  6  камней.  Если  Петя  получил  кучу  из  5  камней (добавил  два  камня),  то  следующим  ходом  Ваня  может  получить  6,  7  или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом  Петя  может  получить  7  или  12  камней.  Получить  8  камней  Петя  не может,  так  как  для  этого  нужно  добавить  2  камня,  а  Петя  делал  это  на предыдущем ходу. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра  завершается, когда количество камней  в куче  становится не менее 21. Победителем  считается  игрок,  сделавший  последний  ход,  то  есть  первым получивший кучу, в которой будет 21 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 20. Будем говорить,  что  игрок  имеет выигрышную  стратегию,  если  он  может выиграть при любых ходах противника.
 
20) Укажите два  значения S,  при  которых у Вани  есть  выигрышная  стратегия,  позволяющая  ему  выиграть  вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом. В  ответе  запишите  найденные  значения  в  порядке  возрастания:  сначала меньшее, затем большее.

 

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

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