Идём к ним?

К кому это, к ним? — спросите Вы. К ним значит к игре ним и нимберам. Но об этом позже, в следующей статье про теорию игр. Пока рассмотрим такую простую игру.

Игры землероек

Крот и землеройка

Задача У крота и землеройки имеется [latex]n[/latex] зёрен чего-то вкусного. Они по очереди съедают любое количество зерен, но не более половины оставшегося количества. Можно съедать только целое число зёрен. Если игрок не может сделать очередной ход, то он считается проигравшим и ему приходится бежать в магазин за следующей порцией вкусных зёрен.
Ненужно пока писать никаких программ. Просто придумайте стратегию поведения для землеройки, которая делает первый ход.

Предварительная подсказка

Если осталось только одно зерно, то это проигрыш.

Подсказка

А если осталось два зерна? Тогда можно съесть одно зерно и у противника будет проигрышная ситуация. Т.е. если [latex]n=2[/latex], то выигрышный ход: 1.
[latex]n=3[/latex] проигрышная ситуация, поскольку съесть можно только 1 и противнику останется 2. А [latex]n=2[/latex] это выигрышная ситуация для противника.
[latex]n=4[/latex] снова наш выигрыш. Мы можем съесть 1 и оставить противнику 3 и он проиграет.
Дальше сами?

А вот теперь можно написать программу определения величины первого выигрышного хода по данному [latex]n[/latex]. Если выигрышного хода нет, то нужно вывести -1.

Протестируйте программу на тех простых примерах, которые мы уже рассмотрели.

Игры землероек 2

Предыдущая задача для землероек оказалась слишком простой. Ответ игроки могли просчитать без всякой программы. Пришлось усложнить условия. На каждом шаге разрешили съедать не более [latex]m[/latex]-й части оставшихся зёрен (вместо половины в предыдущей задаче).
Составьте программу, которая определяет величину первого выигрышного хода по заданным числам [latex]n[/latex] и [latex]m[/latex]. Если выигрышного хода нет, то нужно вывести -1.

Совет

Советую взять карандаш, бумагу и основательно подумать, а не пытаться что-то сразу программировать.

Важная информация от натуралистов. У землероек очень быстрый обмен веществ. Из-за этого они вынуждены практически постоянно есть. Цикл сон-поиск-еда у них повторяется др семидесяти раз в сутки. Это объясняет почему землеройка не может ничего не съесть в свой ход. Хоть и одно зёрнышко но должна съесть. У крота близкие проблемы.

На эту тему опубликовано

WoW 3. Идем к ним? <br />Опубликовал 19/10/2014Куленюк Денис Віталійович
Задача: https://cpp.mazurok.com/word-of-the-week/идём-к-ним/ Изначально я решил написать программу в которой будут соединенны два решения: для задачи в которой можно сесть не более половины ...
WoW 3: Идем к ним? <br />Опубликовал 04/10/2014Іванов Вячеслав Володимирович
Задача Идем к ним? «У крота и землеройки имеется зёрен чего-то вкусного. Они по очереди съедают любое количество зерен, но ...