Тренировочная сессия 3: первая жадность и сортировка по остаткам СЕССИЯ

Что тренируем сегодня

На прошлой тренировке разбирались базовая арифметика и работа с округлением — сегодня поднимаемся на ступеньку выше и встречаемся с первой настоящей жадностью цикла. Жадность — это стратегия, где на каждом шаге берётся локально лучший вариант, и вопрос всегда один: почему локально лучший выбор не портит глобальный результат? Сегодня разбираем два классических довода в пользу жадности — сортировку по возрастанию силы противника и группировку по остатку вместимости — и оба раза доказываем корректность через exchange argument: показываем, что если бы существовал более выгодный порядок действий, его можно было бы преобразовать в жадный без потери качества.

Уровень задач — CF ~1000–1100, обе решаются после короткой сортировки и одного линейного прохода. Здесь тренируется не сложная структура данных, а именно интуиция «когда жадность работает» — она понадобится ещё десятки раз в следующих сессиях.

---

Теория

Жадность и обменный аргумент (проверка «на прочность»). Жадный алгоритм на каждом шаге берёт локально лучший вариант. Но локальная выгода сама по себе ничего не доказывает — жадность нужно обосновать, иначе это просто предположение, которое может провалиться на скрытых тестах.

Когда применять:

• задача просит найти оптимальный порядок действий или оптимальное разбиение (сортировка, распределение);
• честный перебор всех вариантов порядка заведомо слишком медленный.

Как проверить, что жадность верна (обменный аргумент — «а что если поменять местами два элемента?»):

1. Берём любое корректное решение, где два соседних элемента стоят не в жадном порядке.
2. Меняем их местами.
3. Проверяем: результат не ухудшился.
4. Если так для любой такой пары — жадный порядок можно получить из любого решения без потерь, значит он не хуже остальных.

Например, при сортировке по «силе противника» — если в решении стоят рядом слабый противник после сильного, но по правилу жадности должно быть наоборот, меняем их местами и проверяем: суммарный результат не стал хуже.

Где ошибаются: принимают жадную идею «на глаз», без попытки построить обмен или контрпример — интуитивно правильный порядок не всегда оказывается верным при проверке.

---

Задача 1 — CF ~1000 — «Dragons»

Что дано

Герой застрял на уровне игры, где нужно победить всех $n$ драконов ($1 \le n \le 1000$), чтобы пройти дальше. У героя есть сила — целое число $s$ ($1 \le s \le 10^4$). У каждого дракона тоже есть сила $x_i$ ($1 \le x_i \le 10^4$) и бонус $y_i$ ($0 \le y_i \le 10^4$), который герой получает, если побеждает этого дракона.

Правило дуэли: если сила героя строго больше силы дракона — герой побеждает и получает бонус $y_i$ (сила героя увеличивается на $y_i$). Если сила героя не больше силы дракона — герой проигрывает и погибает. Драконов можно побеждать в любом порядке — герой сам выбирает последовательность.

Нужно определить, может ли герой победить всех драконов без единого проигрыша, и вывести YES или NO.

Формат ввода

Первая строка — два целых числа $s$ и $n$. Далее $n$ строк, в каждой — $x_i$ и $y_i$.

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

YES, если героя можно провести через всех драконов без поражений, иначе NO.

Примеры

Разберём на примере

Возьмём первый пример: сила героя s = 2, два дракона — (x=1, y=99) и (x=100, y=0).

Если попробовать напасть на дракона с силой 100 первым — герой проиграет сразу: 2 ≤ 100. Значит, порядок важен. Попробуем начать со слабого дракона (x=1):

Оба дракона побеждены — ответ YES. Интуиция: чем раньше побеждён дракон с низкой силой и высоким бонусом, тем быстрее растёт сила героя для следующих, более сильных драконов.

Идея решения

Алгоритм в одну фразу: отсортировать драконов по силе x по возрастанию и сражаться строго в этом порядке — если на каком-то шаге силы не хватает, ответ NO, если дошли до конца — YES.

Доказательство через exchange argument

Пусть есть корректная последовательность побед, в которой дракон $A$ (сила $x_A$) идёт после дракона $B$ (сила $x_B$), хотя $x_A < x_B$. Покажем, что их можно поменять местами без потери корректности.

Пусть перед боем с $B$ (в исходном порядке) сила героя равна $s'$. Так как порядок был корректным, $s' > x_B$. Поскольку $x_A < x_B < s'$, то $s' > x_A$ тоже верно — значит, драконом $A$ можно было бы победить раньше, на месте $B$, ничего не нарушив. После этой замены сила героя после двух боев не изменится (сумма бонусов $y_A + y_B$ та же, порядок не влияет на итоговую силу после обоих боёв), а на промежуточном шаге сила героя не может уменьшиться относительно исходной последовательности — потому что мы дрались сначала с более слабым драконом, который требует меньше силы для победы. Значит, если исходный порядок был корректным, после обмена местами он останется корректным.

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

Дополнительное наблюдение: раз бонусы $y_i \ge 0$, сила героя никогда не убывает. Значит, если героя не хватает силы для дракона в отсортированном порядке — не хватит и в любом другом порядке (в других порядках сила перед этим драконом будет не больше, чем в отсортированном, потому что накопленный к этому моменту бонус будет не больше).

Псевдокод

прочитать s, n
прочитать список драконов (x[i], y[i]) для i от 1 до n

отсортировать драконов по x по возрастанию
boss_x = максимальный x среди всех драконов (после сортировки — последний)

для каждого дракона (x, y) в отсортированном порядке:
    если s > x:
        s = s + y
    иначе:
        прервать цикл (дальше можно не проверять)

если s > boss_x:
    вывести "YES"
иначе:
    вывести "NO"

Код решения

Комментарии по реализации.

• Сортировка кортежей. Python и C++ — сортировка по умолчанию для tuple/pair уже сравнивает по первому элементу (силе дракона), второй ключ не нужен.
• Ранний выход. Как только силы не хватает на очередного дракона в отсортированном порядке, дальше проверять нечего — break в обоих языках экономит время, хотя при $n \le 1000$ это не критично для лимита.

Проверка на примерах

Крайние случаи

1. Один дракон, силы героя хватает ровно впритык. Например, s = 5, дракон (x=4, y=0). Условие s > x — 5 > 4, строго больше, побеждает. boss_x = 4, 5 > 4 → YES.
2. Равенство сил героя и дракона. s = 5, дракон (x=5, y=100). 5 > 5 — ложно, герой проигрывает сразу (условие строгое «больше», не «не меньше»). Ответ NO.
3. Несколько драконов с одинаковой силой x. Сортировка не гарантирует конкретный порядок между равными по x, но это неважно — бонус всё равно будет получен для всех драконов с одинаковым x, если сила героя превышает этот x хотя бы раз (после первой же победы над драконом этой силы сила героя растёт, и на следующего дракона с той же x условие s > x выполняется ещё увереннее).
4. Максимальные значения ($s, x, y$ все на уровне $10^4$, $n = 1000$). Максимально возможная сила героя — $10^4 + 1000 \cdot 10^4 \approx 10^7$, помещается в int, но в решении используется long long для запаса.

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

1. Проверка s >= x вместо s > x. Условие задачи — «сила героя должна быть строго больше» — при равенстве герой проигрывает.
2. Забыть отсортировать драконов и проверять их в порядке ввода. Порядок из условия произвольный, жадность требует именно сортировки по силе.
3. Использовать сумму всех бонусов заранее, не проверяя промежуточные поражения. Даже если сумма бонусов в итоге даёт силу больше самого сильного дракона, героя может не хватить для промежуточного дракона, если порядок неверный — обязательно проверять каждый шаг, а не только финальную силу.
4. Не прерывать цикл при первом поражении, а продолжать «добавлять» бонусы несуществующих побед. Нужно явно остановиться, как только условие s > x не выполнено, иначе логика посчитает бонус за бой, которого не было.

Сложность

Время: $O(n \log n)$ на сортировку, $O(n)$ на проход. Память: $O(n)$ на хранение списка драконов.

---

Задача 2 — CF ~1100 — «Taxi»

Что дано

Есть $n$ компаний друзей ($1 \le n \le 10^5$), которые решили вместе доехать на такси до места встречи. В $i$-й компании — $s_i$ человек ($1 \le s_i \le 4$). Каждая машина такси вмещает не более четырёх пассажиров. Все участники одной компании должны ехать в одной машине (но одна машина может взять несколько компаний, если хватает мест).

Нужно определить минимальное число такси, которое понадобится, чтобы отвезти всех.

Формат ввода

Первая строка — целое число $n$. Вторая строка — последовательность $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le 4$), через пробел.

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

Одно число — минимальное количество такси.

Примеры

Разберём на примере

Возьмём первый пример: группы размером 1, 2, 4, 3, 3.

• Группа размера 4 — занимает такси целиком, никого больше не подсадить. Такси: [4].
• Каждая группа размера 3 — в машине остаётся ровно 1 свободное место, которое может занять только группа размера 1 (группа размера 2 или 3 туда не влезет). У нас две группы по 3 и одна группа по 1 — одна из троек забирает единицу себе, вторая тройка едет одна. Такси: [3, 1], [3].
• Осталась группа размера 2 — она едет в отдельной машине (пары по 2 обычно комбинируют по две группы в одной машине, но здесь она всего одна). Такси: [2].

Итого: [4], [3,1], [3], [2] — 4 машины. Это и есть ответ.

Интуиция: машины для четвёрок и троек считаются сразу (каждая — минимум одна машина). Дальше нужно жадно «доукомплектовывать» тройки одиночками (это единственный размер, который в них влезает), а остаток единиц и все двойки досчитать отдельно.

Идея решения

Алгоритм в одну фразу: посчитать количество групп каждого размера — cnt[1], cnt[2], cnt[3], cnt[4] — и жадно скомпоновать машины по правилам: cnt[4] — отдельные такси; cnt[3] — отдельные такси, каждая забирает по одной единичной группе, если такие остались; cnt[2] — попарно объединяются по два в одно такси, если осталась одна непарная двойка, ей выделяется отдельное такси (в которое затем можно доподсадить до двух единичных групп); все оставшиеся единичные группы — по 4 штуки в одно такси.

Доказательство через exchange argument

Здесь жадность работает на уровне «выгоднее заполнить машину под завязку, чем оставить свободное место, которое больше нечем занять с меньшими потерями».

Разберём по размерам:

• Группа размера 4 всегда занимает такси одна — тут нет выбора, доказывать нечего.
• Группа размера 3 оставляет ровно одно свободное место. Единственный размер группы, который туда помещается — размер 1 (размер 2 и 3 не влезают: $3 + 2 = 5 > 4$, $3 + 3 = 6 > 4$). Значит, максимум пользы от одного свободного места — подсадить туда одну единичную группу, если такая есть. Если бы мы вместо этого повезли эту единичную группу отдельной машиной, а свободное место в тройке пропало бы — мы бы потратили лишнюю машину. Значит, жадно подсаживать единичку в каждую тройку, пока единички не кончились, — не хуже любой другой стратегии, а по сути единственная стратегия использования этого места.
• Группа размера 2 — две двойки вместе заполняют машину ровно ($2+2=4$), это самый эффективный вариант использования двоек между собой. Если бы мы вместо объединения двух двоек везли каждую отдельно (с довеском единичек), потребовалось бы больше машин на ту же полезную нагрузку — объединение пары двоек строго не хуже. Если количество двоек нечётное, одна остаётся без пары — для неё выделяется отдельная машина, в которую можно доподсадить до двух оставшихся единичных групп ($2+1+1=4$).
• Группа размера 1 — после того как единички разошлись по тройкам и по непарной двойке, оставшиеся единички компонуются по 4 штуки в машину — это максимально плотная упаковка, лучше не бывает.

Формально, это можно записать через инвариант «занятость мест»: суммарное число пассажиро-мест во всех использованных такси не меньше суммы всех $s_i$, и жадная стратегия минимизирует число машин при этом ограничении, потому что на каждом шаге либо заполняет машину полностью (четвёрки, парные двойки, четвёрки единичек), либо использует единственно возможный вариант доукомплектования (тройка + единичка), не оставляя «дешёвых» свободных мест, которые можно было бы использовать эффективнее.

Псевдокод

прочитать n
прочитать массив s из n чисел

cnt[1..4] = 0
для каждого значения v в массиве s:
    cnt[v] += 1

такси = cnt[4] + cnt[3]              // каждая четвёрка и тройка — отдельная машина

// подсаживаем единичек в тройки (по одной на тройку)
подсаженных_единичек = минимум(cnt[1], cnt[3])
cnt[1] -= подсаженных_единичек

// объединяем двойки парами
такси += cnt[2] / 2                  // целочисленное деление
если cnt[2] нечётно:
    такси += 1                       // непарная двойка — своя машина
    // в неё можно подсадить до двух единичек
    cnt[1] = максимум(0, cnt[1] - 2)

// оставшиеся единички — по 4 штуки в машину, округление вверх
такси += (cnt[1] + 3) / 4            // целочисленное деление

вывести такси

Код решения

Комментарии по реализации.

• Счётчик по размеру группы вместо сортировки. Поскольку $s_i \in \{1,2,3,4\}$ — фиксированный диапазон, счётчик cnt[1..4] эффективнее сортировки всего массива: $O(n)$ вместо $O(n \log n)$, хотя при $n \le 10^5$ оба варианта укладываются в лимит.
• Порядок операций важен. Подсадка единичек в тройки должна произойти до обработки двоек и до финального округления единичек — иначе единички, которые могли бы бесплатно занять место в тройке, ошибочно попадут в отдельный подсчёт по 4 штуки.

Проверка на примерах

Пример 1: 1 2 4 3 3 → cnt = [_, 1, 1, 2, 1] (индексы 1..4).

• такси = cnt[4] + cnt[3] = 1 + 2 = 3.
• seated_ones = min(1, 2) = 1 → cnt[1] = 0.
• такси += cnt[2] // 2 = 1 // 2 = 0 → такси = 3. cnt[2] % 2 = 1 → такси += 1 = 4, cnt[1] = max(0, 0-2) = 0.
• такси += (0 + 3) // 4 = 0 → итого 4 ✓

Пример 2: 2 3 4 4 2 1 3 1 → cnt = [_, 2, 2, 2, 2].

• такси = cnt[4] + cnt[3] = 2 + 2 = 4.
• seated_ones = min(2, 2) = 2 → cnt[1] = 0.
• такси += cnt[2] // 2 = 2 // 2 = 1 → такси = 5. cnt[2] % 2 = 0 — без непарной двойки.
• такси += (0 + 3) // 4 = 0 → итого 5 ✓

Крайние случаи

1. Все группы размера 4. Каждая — отдельное такси, cnt[3] = cnt[2] = cnt[1] = 0, ответ равен количеству групп.
2. Одна-единственная группа размера 1. cnt[1] = 1, всё остальное — 0. такси = 0, доукомплектовывать тройки нечем, двоек нет, (1 + 3) // 4 = 1 → ответ 1.
3. Много единичек без троек и двоек, не кратно 4 (например, 5 групп по 1). (5 + 3) // 4 = 2 — две машины (в одной 4 человека, во второй 1). Без +3 (то есть без округления вверх) получилось бы 5 // 4 = 1, что неверно — пятый пассажир остался бы без места.
4. Одна непарная двойка без единичек рядом. cnt[2] = 1, cnt[1] = 0 — непарная двойка получает отдельное такси, cnt[1] = max(0, 0 - 2) = 0 (не уходит в отрицательные значения благодаря max).
5. Троек больше, чем единичек. Например, cnt[3] = 5, cnt[1] = 2 — seated_ones = min(2, 5) = 2, все единички закончились, три тройки едут без подсадки — это ожидаемо: свободные места в тройках, для которых не хватило единичек, останутся пустыми, дополнительных такси это не создаёт (тройка и так уже отдельная машина).

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

1. Забыть про round-up при делении единичек на 4. Формула cnt[1] // 4 (без +3) потеряет последнюю неполную группу — обязательно (cnt[1] + 3) // 4 или эквивалент ceil.
2. Подсадить единичку в тройку больше одного раза. В одну тройку помещается только одна дополнительная единичка (не две — суммарно вместимость 4, тройка уже занимает 3 места).
3. Перепутать порядок обработки — сначала посчитать единички по 4 штуки, а потом пытаться «вычесть» уже отправленных в такси людей из троек. Правильный порядок: сначала тройки забирают единичек, потом остаток единичек считается отдельно.
4. Не проверить, что непарная двойка может забрать до двух единичек, а не одну. В машину с двойкой помещается ещё два места ($2 + 1 + 1 = 4$), а не одно.
5. Использовать int для суммы такси при очень больших n в других похожих задачах по невнимательности — здесь при $n \le 10^5$ ответ не превышает $10^5$, int достаточно, но привычка проверять диапазон суммы окупается в задачах с большими лимитами.

Сложность

Время: $O(n)$ на подсчёт групп по размеру. Память: $O(1)$ дополнительной памяти (счётчик фиксированного размера 5), не считая хранения входного массива.

---

Самостоятельная тренировка

Прорешай эти четыре задачи самостоятельно — они тренируют похожую интуицию: разбор случаев по остатку/делимости и жадное сопоставление после сортировки:

• Codeforces 122A «Lucky Division» (~CF 1000) — определить, делится ли число нацело хотя бы на одно «счастливое» число (число, состоящее только из цифр 4 и 7).
• Codeforces 456A «Laptops» (~CF 1100) — по списку пар «цена–качество» ноутбуков определить, существует ли пара, где более дорогой ноутбук имеет более низкое качество.
• Codeforces 90A «Cableway» (~CF 1000) — по числу людей, ожидающих одну из трёх циклически чередующихся кабинок фуникулёра, определить, сколько минут понадобится, чтобы поднять всех наверх.
• Codeforces 285A «Slightly Decreasing Permutations» (~CF 1100) — по длине перестановки $n$ и заданному «коэффициенту убывания» $k$ построить любую перестановку длины $n$ с ровно $k$ позициями, где следующий элемент меньше предыдущего.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

На следующей тренировке остаёмся рядом по уровню (CF ~1100) и добавляем новый инструмент — сортировку в связке с бинарным поиском и первое знакомство с суффиксными массивами.