Жадный exchange argument и формула за O(1) — задача «Шашлык для методкомиссии» РАЗБОР

Источник задачи: региональный этап Олимпиады им. М.В. Келдыша, 2025, задача A.

Что дано

У комиссии есть мангал с начальной температурой t. Готовят два вида шашлыка:

Порции можно готовить в любом порядке, общее число порций не ограничено. Задача — приготовить как можно больше порций суммарно с учётом того, что перед каждой новой порцией температура мангала должна быть не меньше её порога. Между порциями температура может уйти в ноль или в минус — это допустимо, ограничение проверяется только перед началом готовки очередной порции.

Ограничения

• $0 \leq t \leq 10^{12}$, $1 \leq a, b, x, y \leq 10^{12}$
• Ответ может превысить $2^{31}$, поэтому арифметику вести в 64-битных целых (long long в C++, обычный int в Python).

Формат ввода

Пять натуральных чисел, каждое в отдельной строке: t, a, b, x, y (именно в таком порядке).

Формат вывода

Одно целое число — максимальное число порций.

Примеры

Разберём первый пример руками

t = 10, a = 3, x = 2, b = 4, y = 1

Что это значит:

• Мангал изначально горячий (10°).
• Вид 1 требует 3°, уносит 2° (то есть «охлаждает сильно», но порог низкий).
• Вид 2 требует 4°, уносит 1° (порог выше, но охлаждает мягко).

Попробуем стратегию «чередуем вслепую»: вид 1, вид 2, вид 1, вид 2…

Итого — 5 порций. Неплохо, но ответ, как сейчас увидим, 8.

Попробуем «сначала все виды 2, потом виды 1»:

Итого — 8 порций. Вот оно.

Интуиция, которая только что появилась в голове: выгодно сначала готовить тот вид, который охлаждает мангал меньше. У нас это вид 2 — он уносит всего 1° против 2° у вида 1. Каждая «единица охлаждения» — это потенциальная потеря будущих порций. Лучше тратить температуру по чайной ложке, чем сразу большими порциями.

---

Идея решения: жадность по минимальному охлаждению

Алгоритм в одну фразу:

Сначала готовим максимальное число порций того вида, у которого меньше охлаждение. Затем — максимальное число порций другого вида.

Чтобы не возиться с двумя случаями, договоримся: вид 1 у нас всегда экономный (тот, что меньше охлаждает). Если в условии оказалось наоборот — просто поменяем виды местами, ответ от этого не изменится. Тогда план такой:

1. Готовим столько вида 1, сколько позволяет температура.
2. Готовим столько вида 2, сколько позволяет оставшаяся температура.
3. Сумма — ответ.

Почему жадность работает?

Температура — общий ресурс. Каждая порция его тратит. Чем меньше порция тратит — тем больше таких порций в целом помещается в один и тот же мангал. Значит, «экономный» вид всегда эффективнее: из одной и той же температуры его порций получится больше, чем «прожорливого».

Поэтому логика простая: сначала выжимаем максимум из экономного, остатки отдаём прожорливому. Если сделать наоборот — прожорливый вид сожжёт температуру, которой хватило бы на несколько порций экономного. Эту потерю уже не вернуть — пустая потраченная температура обратно не появляется.

Сколько порций одного вида можно приготовить из температуры T?

Допустим, есть температура $T$, порог $p$ и охлаждение $d$. Если $T < p$ — не приготовим ничего, нечего и считать. Если $T \geq p$ — одну порцию точно сделаем, после неё останется $T - d$.

Дальше думаем так: над порогом $p$ у нас «лишних» $T - p$ градусов сверх минимума. Каждая следующая порция отъедает от этого запаса по $d$. Сколько раз $d$ помещается в $T - p$ — столько ещё порций мы и приготовим (округление вниз, потому что недоеденный кусок $d$ нам не помогает). Плюс самая первая, которая помещается «бесплатно».

Итого формула одной строкой:

$$k = \left\lfloor \frac{T - p}{d} \right\rfloor + 1, \quad \text{если } T \geq p; \quad \text{иначе } k = 0.$$

Округление вниз — это обычное целочисленное деление: // в Python, / для положительных long long в C++.

---

Решение: псевдокод

ввести t, a, b, x, y

# Хотим, чтобы x <= y (вид 1 — экономный)
если x > y:
    поменять местами (a, x) и (b, y)

# Считаем, сколько порций вида 1 готовим
# (// — целочисленное деление с округлением вниз)
если t >= a:
    k1 = (t - a) // x + 1
    t = t - k1 * x
иначе:
    k1 = 0

# Считаем, сколько порций вида 2 готовим из оставшейся t
если t >= b:
    k2 = (t - b) // y + 1
иначе:
    k2 = 0

вывести k1 + k2

Это $O(1)$ — несколько арифметических операций.

---

Код решения

Переключи вкладку, чтобы посмотреть второй язык. В Python про переполнение int думать не надо — он неограниченной точности. В C++ обязателен long long везде: значения до $10^{12}$, в int не поместятся.

---

Проверим на всех примерах из условия

Пример 1

t=10, a=3, x=2, b=4, y=1

• $x=2 > y=1$, меняем: теперь $a=4, x=1, b=3, y=2$.
• $t=10 \geq a=4$: $k_1 = (10-4)/1 + 1 = 7$. $t = 10 - 7 = 3$.
• $t=3 \geq b=3$: $k_2 = (3-3)/2 + 1 = 1$.
• Ответ: 7 + 1 = 8 ✓

Пример 2

t=1, a=10, b=10, x=1, y=1

• $x = y$, меняем или нет — всё равно.
• $t=1 < a=10$: $k_1 = 0$.
• $t=1 < b=10$: $k_2 = 0$.
• Ответ: 0 ✓

Пример 3

t=28, a=14, b=5, x=2, y=4

• $x=2 < y=4$, не меняем.
• $t=28 \geq a=14$: $k_1 = (28-14)/2 + 1 = 8$. $t = 28 - 16 = 12$.
• $t=12 \geq b=5$: $k_2 = (12-5)/4 + 1 = 2$.
• Ответ: 8 + 2 = 10 ✓

Всё сходится.

---

Крайние случаи, на которых можно споткнуться

Эти случаи тесты олимпиады почти наверняка проверяют. Перед отправкой убедись, что код их обрабатывает.

1. Изначально холодный мангал

t=5, a=10, b=10, x=1, y=1

Ответ — 0. Если посчитаешь $(5 - 10) / 1 + 1 = -4$ (или что-то странное при переполнении) — значит забыл проверить $t \geq a$ и $t \geq b$. В коде выше проверка есть.

2. Температура может стать сильно отрицательной

t=100, a=1, b=100, x=1000000000000, y=1

• $x=10^{12} > y=1$, меняем: $a=100, x=1, b=1, y=10^{12}$.
• $k_1 = (100-100)/1 + 1 = 1$. $t = 100 - 1 = 99$.
• $k_2 = (99-1)/10^{12} + 1 = 0 + 1 = 1$.
• Ответ: 2. Температура после: $99 - 10^{12} = -999\,999\,999\,901$. Это не проблема — ограничение проверялось до готовки.

3. Оба вида с одинаковым охлаждением

Допустим $x = y$. Тогда порядок не важен, но по коду $x > y$ ложно, значит не меняем. Готовим сначала вид 1. Если $a < b$ — начнём с вида 1 (у которого ниже порог), потом добьём вид 2 — это тоже оптимально, так как при равном охлаждении работает любая разумная стратегия.

Проверь сам: $t=10, a=1, b=5, x=2, y=2$ → ожидаемый ответ: $k_1 = (10-1)/2+1 = 5$, $t = 10-10 = 0$, $k_2 = 0$ (так как $0 < 5$). Итого 5.

Альтернатива: сначала вид 2. $k_2 = (10-5)/2+1 = 3$, $t = 10-6 = 4$, $k_1 = (4-1)/2+1 = 2$. Итого 5. Одно и то же.

4. Границы ограничений

$t = a = b = x = y = 10^{12}$ → $k_1 = (10^{12} - 10^{12})/10^{12} + 1 = 1$, $t = 0$, $k_2 = 0$. Ответ: 1. long long вмещает ~$9.2 \cdot 10^{18}$, так что запас огромен.

---

Типичные ошибки

1. int вместо long long в C++. Значения до $10^{12}$, в int (макс. ~$2 \cdot 10^9$) не поместятся. В Java — использовать long, а не int.

2. Забыл поменять $(a, x)$ и $(b, y)$ местами, когда $x > y$. Частая ошибка: меняют только $x$ и $y$, но не $a$ и $b$. Порог привязан к виду — если меняешь охлаждение, меняй и порог.

3. Неверная формула для количества порций. Типичный баг: $k = (T - p) / d$ (без +1). Тогда упустишь одну порцию в нижней границе. Проверяй: если $T = p$, то $k = (p - p)/d = 0$ (без +1) — но одна порция ведь помещается ($T \geq p$)! Правильно: $k = (T - p)/d + 1$.

4. Деление в Python через / вместо //. В Python 3 / — это float-деление, оно вернёт 7.0 вместо 7. Используй // для целого.

5. Проверка t > a вместо t >= a. При $t = a$ одна порция помещается: перед готовкой температура ровно $a$, условие «≥ $a$» выполняется.

6. Моделирование «по одной порции» в цикле. Теоретически работает, но при $t = 10^{12}$ и $x = 1$ цикл сделает $10^{12}$ итераций — это секунды или минуты, а дают 1 секунду на тест. Формула — $O(1)$, цикл — $O(k) = O(10^{12})$. Не рассчитывай на лимит времени — используй формулу.

---

Анализ сложности

• Время: $O(1)$. Несколько арифметических операций, не зависящих от значений переменных.
• Память: $O(1)$.

---

Что ещё полезно потренировать

Задачи с похожей идеей — «жадный выбор по наименее затратному варианту» (в олимпиадной классификации: greedy + exchange argument):

• Codeforces 230A «Dragons» — сортировка драконов по силе, жадный подход к порядку поглощения. Базовый пример жадности.
• Codeforces 137B «Permutation» — жадность по разности между массивом и оптимальной перестановкой.
• Codeforces 556A «Case of the Zeros and Ones» — жадное сокращение «01» и «10» пар.
• acmp.ru задача 186 «Два мешка» — жадный выбор, аналогичная конструкция.

После решения 3–5 таких задач (разными способами) интуиция «когда работает жадность и как её доказать через exchange argument» закрепляется — и следующая «греди» задача на олимпиаде решается за минуты.

---

Итого

• Идея: жадно, сначала вид с меньшим охлаждением, пока можно, потом другой.
• Формула количества порций из температуры $T$ с порогом $p$ и охлаждением $d$:

$$k = \left\lfloor \frac{T - p}{d} \right\rfloor + 1, \text{ если } T \geq p; \quad \text{иначе } k = 0.$$

• Сложность: $O(1)$.
• Ловушки: переполнение int (нужен long long), off-by-one в формуле (не забыть +1), забыть поменять пары $(a,x)$ и $(b,y)$ одновременно.