Шешімі: Камни и выигрышная стратегия
Құжат тапсырмағаИнструкция к заданиям по информатикаға
Прочитайте текст и выполните тапсырмалар.
Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу 1 или 3 камня либо увеличить количество камней в куче в 2 раза. Игра завершается, когда количество камней становится не менее 435. Побеждает игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, $1 \leq S \leq 434$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Шешім по шагам
3 қадамПетя не должен выигрывать первым ходом, поэтому после каждого его возможного хода количество камней должно быть меньше 435. В частности, при $S=217$ это выполняется: $218$, $220$ и $434$.
Чтобы Ваня мог выиграть одним ходом из позиции $x$, достаточно, чтобы $2x \geq 435$, либо чтобы $x+3 \geq 435$, либо чтобы $x+1 \geq 435$. Наименьшая подходящая позиция — $x=218$, так как $2 \cdot 218=436$.
Минимальный результат хода Пети равен $S+1$, поэтому требуется $S+1 \geq 218$, то есть $S \geq 217$. При $S=217$ после ходов Пети получаются позиции 218, 220 и 434; Ваня может удвоить 218, добавить 3 к 220 или добавить 1 к 434.
Где здесь ошибаются
Учитывают только ход с удвоением количества камней и не проверяют ходы с добавлением 1 или 3 камней.
Выбирают значение, при котором Петя сам может получить 435 или больше первым ходом.
Проверяют только один возможный ход Пети вместо всех трёх.