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-м ходом)

F(S, 2)

минимальное S

20 (Петя выигрывает 2-м ходом)

F(S, 3) and not F(S, 1)

два наименьших S

21 (Ваня выигрывает 2-м ходом)

F(S, 4) and not F(S, 2)

наименьшее S

«Неудачный ход» (есть плохой ход Пети)

у Пети all → any

минимальное 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. Перепутал any и all. Запомни: свой ход — any, ход соперника — all. Ошибка тут переворачивает ответ.

2. Забыл not F(S, 1) в задании 20 или not F(S, 2) в задании 21 — и в список попадают «лишние» позиции, где выигрыш происходит на ход раньше.

3. Неправильный порог. В «растущей» игре s >= FIN, в «убывающей» — s <= FIN. Перепутаешь знак — весь ответ мимо.

4. Написал s / 4 вместо s // 4. Обычное деление даёт дробь, а в игре камни целые — только целочисленное //.

5. Не тот вопрос из прототипа. 19 — обычно минимальное, 20 — два наименьших, 21 — наименьшее из нескольких. Читай последнюю строку условия.

6. Пропустил «неудачный ход». Если в 19 написано «после неудачного хода Пети» — это any у Пети, а не all. Стандартный код даст неверный (часто пустой) ответ.

7. Слишком узкий range. Для убывающих игр и двух куч бери диапазон с запасом, иначе не увидишь все подходящие S.

💡 Последнее напутствие

Задания 19–21 — самый «шаблонный» блок второй части. Разобрался с одной игрой — разобрался со всеми: меняешь ходы и порог, крутишь F(S, 2), F(S, 3), F(S, 4) — и три балла у тебя в кармане. Главное — не заучивать код бездумно, а понимать, где any, а где all, и что именно спрашивает каждый прототип.

Тренируйся на реальных вариантах — игры разные, а шаблон один. Удачи на экзамене — Профиматика с тобой!