Каталог: Задания №19–21. Игра с камнями: код Кабанова
Спецификация и суть задания №20
Одна игра и три вопроса про начальное количество камней S. Мы пишем короткую функцию, которая умеет проверять «кто выигрывает за m ходов», и тремя вызовами отвечаем на все три вопроса.
Основные прототипы и разновидности
Состояние это одно число. Ходы: добавить камни, убрать, умножить или разделить.
Состояние это пара (a, b). Ход меняет одну из куч, игра кончается по сумме камней.
Например, удвоение запрещено, когда кучи равны. Такое условие попадает в функцию moves.
Теоретический фундамент и алгоритмы
Что от тебя хотят
Петя и Ваня по очереди ходят в игре с камнями, Петя первый. Есть правила ходов и порог, при достижении которого игра заканчивается. Выигрывает тот, кто сделал последний ход. Начальное количество камней S неизвестно, и про него задают три вопроса. В экзамене это задания 19, 20 и 21, а в нашем банке они собраны в один блок с одной игрой и тремя вопросами.
Три вопроса и что вызвать
| Как звучит вопрос | Что проверить в коде |
|---|---|
| №19. Петя не может выиграть первым ходом, но при любом его ходе Ваня выигрывает своим первым ходом | f(S, 2) |
| №19, вариант «возможно». Ваня выиграл первым ходом после неудачного хода Пети: при каком S это возможно | any(f(x, 1) for x in moves(S)) |
| №20. У Пети есть стратегия: за один ход он не выигрывает, но выигрывает вторым ходом при любой игре Вани | f(S, 3) and not f(S, 1) |
| №21. Ваня выигрывает первым или вторым ходом при любой игре Пети, но не может гарантированно выиграть первым | f(S, 4) and not f(S, 2) |
Идея Кабанова: считаем ходы по одному
Функция f(h, m) отвечает на вопрос «чем кончится игра, если сделать не больше m ходов». Вызываем её всегда для начального положения, когда ходит Петя. Тогда:
- если m нечётное, ответ
Trueозначает «выигрывает Петя»; - если m чётное, ответ
Trueозначает «выигрывает Ваня».
Внутри функции три строки: «если игра кончилась, засчитываем победу тому, кто сделал последний ход»; «если ходы закончились, никто не выиграл»; «иначе пробуем все ходы». Для нашего игрока достаточно одного хорошего хода (any), а противника придётся проверить на любой ход (all).
moves (какие ходы бывают) и условие конца игры. Весь остальной код переписывать не придётся ни в одной задаче.
Разбор 1: одна куча
Куча из S камней, S ≥ 3215. За ход можно убрать 4 камня, убрать 5 камней или уменьшить число камней в 3 раза (с округлением вверх). Игра заканчивается, когда в куче не более 3214 камней. Вопрос 1: сумма всех S, при которых выполнено условие №19. Вопрос 2: наименьшее и наибольшее S из №20. Вопрос 3: сколько значений S подходит под №21.
В левом окне округление вверх записано как (h + 2) // 3. Ответы: 38578, 9647 и 28938, 8. Они совпадают с ответами из банка.
Разбор 2: две кучи
Две кучи: в первой 6 камней, во второй S (от 1 до 93). За ход можно добавить в любую кучу один камень или увеличить любую кучу в четыре раза. Игра заканчивается, когда в двух кучах вместе не меньше 100 камней. Три вопроса те же.
Состояние теперь пара (a, b), ходы возвращают пары, конец игры по sum(h). Правое окно даёт ответы 4, 3 и 23, 22. Первый вопрос здесь в варианте «возможно», поэтому в нём стоит any по первому ходу Пети.
(h + 2) // 3 для деления на 3 и (h + k - 1) // k для любого k. Обычное // округляет вниз и даёт другой ответ.
Лайфхаки и фишки для ускорения
Для двух куч состояние хранится кортежем (a, b): списки нельзя класть в lru_cache, кортежи можно.
Диапазон S бери из условия: для одной кучи начни с порога плюс один, для двух возьми диапазон второй кучи.
Сначала проверь функцию на очень маленькой игре, где исход можно разобрать руками: например, куча до 5 камней и ходы +1 и ×2.
Частые ошибки и экзаменационные ловушки
TrueПри нечётном
m в f True значит победу Пети, при чётном победу Вани.
m и держи в голове таблицу: №19 это m = 2, №20 m = 3, №21 m = 4.
not f(S, 1) во втором и третьем вопросахВ ответ попадут значения S, где Петя (или Ваня) выигрывает слишком рано.
and not f(S, 1) и and not f(S, 2).
Если при равных кучах удвоение запрещено, а в
moves оно осталось, ответ окажется неверным.
moves: условие if a == b внутри функции.
Бывает, что одну из куч нельзя трогать при определённом условии, или что ход зависит от того, какая куча больше. Тогда набор ходов у разных позиций получается разный.
Практические задачи из банка КИМ (Всего: 0)
Решать в песочнице СмартКИМГотовьтесь к ЕГЭ эффективно со СмартКИМ
Составляйте индивидуальные пробники, решайте задачи в онлайн-песочнице со встроенным компилятором Python и Web-Excel, отслеживайте статистику и делитесь результатами с учителем.
Собрать вариант КИМ