Задания 19–21 · Выигрышная стратегия
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — игра с двумя кучами, ходы «+3» и «×2» до 100 и три вопроса 19–21 — прошла через подтемы, и каждая добавляла к решению новый шаг. Пролистай черновик: точками отмечены строки, которых не было после предыдущей подтемы.
- Подтема 1, «Игра и вопросы 19–21»: возможность или гарантия. Точками отмечены новые строки.
- Подтема 2, «Позиции от конца»: группы от конца игры.
- Подтема 3, «Программа»: any — свой ход, all — соперника.
- Подтема 4, «Две кучи»: позиция — пара куч. Ответы задачи темы: 24; 23 42; 39.
Функция g не меняется от игры к игре — меняются только moves и finished. Подтема 5 переносит её на уменьшение кучи и ходы с условием, а дополнительный урок — на третий ход и позиции шире одного числа.
Карта темы
Каждая подтема дала одно правило, и любое решение собирается из них. Сверху — путь от условия к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Правилаmoves и finished дословно по условию
- ГруппыВ1, П1, В2, П2 от конца игры
- Ответперебор S и то, что просят
1Игра и вопросы 19–21
- свой ходхватает одного удачного
- ход соперникагодиться должны все его ходы
- неудачный ход Петивозможность, а не гарантия
2Позиции от конца игры
- В1есть ход, который кончает игру
- П1все ходы ведут в В1
- В2не В1, есть ход в П1 — задание 20
- П2не П1, все ходы в В1 или В2 — задание 21
3Программа
any / allсвой ход / ход соперника@cacheкаждая позиция считается один разmistakeнеудачный ход Пети — задание 19
4Две кучи
- (a, b)позиция — пара, а не сумма
- четыре ходакаждая операция с каждой кучей
5Уменьшение кучи и ходы с условием
s // 2округление вниз; вверх — (s + 1) // 2- наибольшее Sграница — самый быстрый путь до порога
6Третий ход и позиция шире числадополнительный урок
- В3, П3ещё один шаг от конца
- (s, last)позиция помнит последний ход
Как решать
Любые задания 19–21 решаются одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Частые ошибки
Семь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- партия вместо стратегии
- нашли удачную партию — победа гарантирована → на ходе соперника проверяют все его ходы. Спроси себя: а если соперник ответит иначе?подтема 1
- неудачный ход как гарантия
g(s) == -1→mistake(s). Спроси себя: спрашивают о гарантии или о возможности?подтема 1- второй ход
- «Петя выиграл вторым ходом» — два хода игры → второй ход Пети — третий ход игры. Спроси себя: чей это ход по счёту?подтема 2
- сравнение в finished
a + b > 100→a + b >= 100. Спроси себя: «не менее» — это ≥?подтема 3- сумма вместо пары
- позиция двух куч — их сумма → позиция — пара (a, b). Спроси себя: одинаковы ли ходы из (7, 10) и (10, 7)?подтема 4
- округление
round(s / 2)→s // 2. Спроси себя: вниз или вверх сказано в условии?подтема 5- граница для наибольшего
- наибольшее S — перебором до случайного числа → граница — самый быстрый путь до порога. Спроси себя: почему больше S не бывает?подтема 5
Итог
Тема пройдена: задача темы решена от смысла вопросов до ответов 24; 23 42; 39. Вот что взять с собой.
- ПорядокПравила, вопрос, группы, программа, ответ.
- ХодыСвой — хватит одного, соперника — все.
- ГруппыВ2 — задание 20, П2 — задание 21, mistake — 19.
- ПрограммаМеняются только moves и finished.
- Задача темы19 — 24, 20 — 23 и 42, 21 — 39.
Проверьте себя
Ответь сначала сам, потом открой ответ.
В позиции все ходы ведут в позиции В1. Кто выигрывает и к какой группе она относится?
ОтветСкрыть ответ
П1: какой бы ход ни сделал игрок, соперник сразу заканчивает игру.
Чем вопрос задания 19 отличается от заданий 20 и 21?
ОтветСкрыть ответ
В 19 — возможность: Петя ошибся, хватит одной такой партии. В 20 и 21 — гарантия при любой игре соперника.
Почему в программе свой ход проверяют через any, а ход соперника — через all?
ОтветСкрыть ответ
Игроку достаточно одного удачного хода, а против соперника должны сработать все его ответы.
Сколько ходов из позиции (7, 10) в задаче темы?
ОтветСкрыть ответ
Четыре: (10, 10), (14, 10), (7, 13), (7, 20).
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
+2 или ×3: неудачный ход Пети
Два игрока, Петя и Ваня, играют в игру с кучей камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в три раза. Игра завершается, когда количество камней в куче становится не менее 70. Победителем считается игрок, сделавший последний ход. В начальный момент в куче было S камней, 1 ≤ S ≤ 69. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Введите число.
Подсказка
Два утроения подряд — самый быстрый рост.
Решение
два утроения дают 8 · 3 · 3 = 72 ≥ 70, а 7 · 9 = 63; с прибавлением меньше: (7 + 2) · 3 = 27.
from functools import cache def moves(s): return [s + 2, s * 3] def finished(s): return s >= 70 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(x > 0 for x in r): return -2 # П2 return 0 def mistake(s): # Петя ходит так, что Ваня выигрывает сразу return any(not finished(q) and g(q) == 1 for q in moves(s)) print(min(s for s in range(1, 70) if mistake(s)))Ответ: 8
Задание 20: наименьшее и наибольшее
Игра с кучей камней: за один ход можно добавить один камень, добавить три камня или удвоить кучу. Игра завершается, когда в куче не менее 45 камней, 1 ≤ S ≤ 44. Найдите наименьшее и наибольшее значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани.
Введите два числа через пробел: наименьшее, затем наибольшее.
Подсказка
Собери все В2 и возьми наименьшее и наибольшее.
Решение
11 и 21: подходят 11, 19 и 21.
from functools import cache def moves(s): return [s + 1, s + 3, s * 2] def finished(s): return s >= 45 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(x > 0 for x in r): return -2 # П2 return 0 found = [s for s in range(1, 45) if g(s) == 2]print(min(found), max(found))Ответ: 11 21
Две кучи: задание 21
Две кучи камней: за один ход можно добавить в одну из куч два камня или удвоить одну кучу. Игра завершается, когда суммарное количество камней в кучах становится не менее 100. В первой куче 7 камней, во второй — S, 1 ≤ S ≤ 92. Найдите минимальное значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Введите число.
Подсказка
Начальная позиция (7, S), отбор g(p) == -2.
Решение
подходят 40 и 43.
from functools import cache def moves(p): a, b = p return [(a + 2, b), (a * 2, b), (a, b + 2), (a, b * 2)] def finished(p): a, b = p return a + b >= 100 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(x > 0 for x in r): return -2 # П2 return 0 starts = [(7, s) for s in range(1, 93)]print(min(p[1] for p in starts if g(p) == -2))Ответ: 40
Уменьшение кучи: наибольшее S
Куча камней: за один ход можно убрать три камня, убрать четыре камня или уменьшить количество камней в два раза с округлением вниз. Игра завершается, когда в куче становится не более 40 камней; S ≥ 41. Укажите максимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Введите число.
Подсказка
Граница: самый медленный ход −3 должен вести в В1.
Решение
84: В1 — до 81 (81 // 2 = 40), а каждый ход Пети должен вести в В1; самый медленный ход −3 даёт S − 3 ≤ 81. Подходят 82, 83 и 84.
from functools import cache def moves(s): return [s - 3, s - 4, s // 2] def finished(s): return s <= 40 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(x > 0 for x in r): return -2 # П2 return 0 print(max(s for s in range(41, 1000) if g(s) == -1))Ответ: 84
Победа третьим ходом
Куча камней: за один ход можно добавить один камень, добавить четыре камня или утроить кучу. Игра завершается, когда в куче не менее 100 камней, 1 ≤ S ≤ 99. Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: Петя не может выиграть за один ход; Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Введите два числа через пробел в порядке возрастания.
Подсказка
В2: сразу не выиграть, но можно отдать Ване П1.
Решение
11 и 29: из этих позиций Петя отдаёт Ване П1.
from functools import cache def moves(s): return [s + 1, s + 4, s * 3] def finished(s): return s >= 100 @cachedef g(s): nxt = moves(s) if any(finished(q) for q in nxt): return 1 # В1 r = [g(q) for q in nxt] if all(x == 1 for x in r): return -1 # П1 if -1 in r: return 2 # В2 if all(x > 0 for x in r): return -2 # П2 return 0 print(*[s for s in range(1, 100) if g(s) == 2][:2])Ответ: 11 29