5 Шпаргалка по заданиям 19–21
Шпаргалка по заданиям 19–21
Универсальный скелет — одна куча
def F(s, p):
if s >= FIN: # FIN — порог из условия (или s <= FIN для убывающей игры)
return p % 2 == 0
if p == 0:
return False
hod = [F(s + a1, p - 1), ...] # все ходы из условия (+, ×, −, //)
return any(hod) if p % 2 == 1 else all(hod)
print([s for s in range(1, FIN) if F(s, 2)]) # 19
print([s for s in range(1, FIN) if F(s, 3) and not F(s, 1)]) # 20
print([s for s in range(1, FIN) if F(s, 4) and not F(s, 2)]) # 21Универсальный скелет — две кучи
def F(a, b, p):
if a + b >= FIN:
return p % 2 == 0
if p == 0:
return False
hod = [F(a + 1, b, p - 1), F(a * 2, b, p - 1),
F(a, b + 1, p - 1), F(a, b * 2, p - 1)]
return any(hod) if p % 2 == 1 else all(hod)Таблица «вопрос → вызов»
Прототип | Вызов | Что берём из списка |
|---|---|---|
19 (Ваня выигрывает 1-м ходом) |
| минимальное S |
20 (Петя выигрывает 2-м ходом) |
| два наименьших S |
21 (Ваня выигрывает 2-м ходом) |
| наименьшее S |
«Неудачный ход» (есть плохой ход Пети) | у Пети | минимальное S |
Как читать чётность p
Нечётное p (
1, 3) — ход того, кто хочет выиграть →any(достаточно одного хода).Чётное p (
2, 4) — ход соперника →all(нужно, чтобы любой ход вёл к победе).База
s >= FIN: return p % 2 == 0— если игра уже кончилась, чётное p означает «выиграл наш».
Полезные приёмы
s * 2 # удвоение — самый «дальнобойный» ход в растущей игре
s // 4 # деление С ОКРУГЛЕНИЕМ ВНИЗ (не s / 4!)
[s for s in range(1, N) if …] # перебор всех стартовых позиций одной строкой
min(otv), otv[:2] # минимальное / два наименьших из найденного⚠️ Типичные ошибки 1. Перепутал 2. Забыл 3. Неправильный порог. В «растущей» игре 4. Написал 5. Не тот вопрос из прототипа. 19 — обычно минимальное, 20 — два наименьших, 21 — наименьшее из нескольких. Читай последнюю строку условия. 6. Пропустил «неудачный ход». Если в 19 написано «после неудачного хода Пети» — это 7. Слишком узкий |
💡 Последнее напутствие Задания 19–21 — самый «шаблонный» блок второй части. Разобрался с одной игрой — разобрался со всеми: меняешь ходы и порог, крутишь Тренируйся на реальных вариантах — игры разные, а шаблон один. Удачи на экзамене — Профиматика с тобой! |