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

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

«Разогрев» закончился: восемь сессий вернули беглость в базовых инструментах — формула, сортировка, бинарный поиск, префиксные суммы, хэш-таблица. Начиная с этой сессии мы на «Плато»: коридор сложности поднимается до ~CF 1400–1800, и меняется не столько техника, сколько характер работы. В «Разогреве» приём в задаче был виден почти сразу, оставалось его аккуратно применить. Здесь приём нужно сначала найти — условие маскирует его под что-то другое, а очевидный подход честно работает, но не укладывается по времени.

Сегодняшний приём — жадность по разрядам. Общая идея: число в условии ведёт себя не как величина, которую можно посчитать формулой, а как последовательность цифр, и ответ получается по одной позиции за раз. Обе задачи сессии на него, но берут его с разных сторон: в первой число надо собрать с нуля, во второй — подправить уже данное. Коридор ~CF 1400–1500, нижняя граница фазы: это ещё не тот уровень, где приходится комбинировать три техники в одной задаче, но уже тот, где неверно выбранный подход даёт превышение лимита времени, а не просто некрасивый код.

---

Теория

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

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

• в условии есть слова «наименьшее число», «наибольшее число», «лексикографически минимальный/максимальный ответ» — или «минимальная добавка, после которой свойство выполнится»;
• ограничение задано суммарно по всем цифрам: сумма цифр, количество каких-то цифр, делимость;
• перебрать все варианты нельзя — длина ответа до десятков и сотен знаков, и в числовой тип он может не поместиться.

У приёма две формы, и различать их полезно: число либо собирают с нуля, либо подправляют уже данное. Механика одна — идём по разрядам и на каждом принимаем локальное решение, — но направление обхода и критерий выгоды разные. Сегодня по одной задаче на каждую форму.

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

Как строить:

1. Сначала проверить, существует ли ответ вообще: посчитать минимально и максимально достижимое значение ограничения при данной длине.
2. Идти по разрядам от старшего к младшему.
3. На каждом разряде взять самую выгодную цифру, при которой оставшуюся часть ещё можно достроить (для максимума — самую большую, для минимума — самую маленькую).
4. Отдельно обработать старший разряд: там нельзя поставить ноль.

Мини-пример — длина 3, сумма цифр 20. Максимум: 9, ещё 9, остаток 2 → 992. Минимум: в старший разряд хочется 1, но тогда на два оставшихся разряда нужно набрать 19, а больше 18 они не дают, — значит старший разряд минимум 2, и получается 299.

Каркас приёма — минимальное число длины length с суммой цифр total (существование ответа проверено заранее):

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

Форма 2 — подправить уже данное число. Число n дано, нужное свойство на нём не выполняется, и требуется ближайшее подходящее сверху. Здесь идём наоборот — от младшего разряда к старшему, обнуляя всё более длинный хвост.

Как править:

1. Проверить исходное число: если свойство уже выполнено, добавка нулевая.
2. Округлить вверх до кратного 10 — то есть обнулить последний разряд, добавив единицу к предыдущему. Если число уже кратно 10, оно не меняется.
3. Проверить свойство. Не выполнено — округлить вверх до кратного 100, затем 1000, и так далее.
4. Первое подошедшее число и есть ответ; сама добавка — разность с исходным.

Мини-пример — n = 217, нужна сумма цифр не больше 3. Сейчас 2 + 1 + 7 = 10, много. Округляем до кратного 10 → 220, сумма 4 — всё ещё много. До кратного 100 → 300, сумма 3 — подходит. Добавка 300 − 217 = 83.

Почему достаточно проверять только такие «круглые» кандидаты, а не все числа подряд. Пусть m — верный ответ, то есть наименьшее число не меньше n с нужным свойством, и пусть m > n. Возьмём самый старший разряд, в котором m и n различаются: выше него цифры совпадают, а в нём у m цифра больше — иначе m оказалось бы меньше n. Теперь построим число из старшей части n, увеличенной на единицу цифры в этом разряде и нулевого хвоста. Оно не меньше n и не больше m. Сумма цифр у него не больше, чем у m: старшая часть та же, цифра в разряде не больше, а нулевой хвост ничего не добавляет — значит свойство на нём тоже выполнено. Но m было минимальным, поэтому построенное число и есть m. Отсюда вывод: ответ всегда имеет вид «округлить n вверх до кратного $10^k$», и остаётся перебрать k от нуля до 19.

Каркас приёма — минимальная добавка к n, после которой сумма цифр не больше s:

Где ошибаются в узнавании второй формы: начинают перебирать добавку по единице, пока свойство не выполнится. Ответ при этом верный, но добавка бывает порядка $10^{18}$, и цикл не заканчивается никогда. Признак, что нужен переход к «круглым» кандидатам, — огромный разброс ответа при крошечном числе разрядов.

Где приём перестаёт работать. Обе формы опираются на то, что ограничение складывается из разрядов независимо — сумма цифр, количество каких-то цифр, — и потому проверяется на лету. Как только ограничение связывает разряды нелинейно («делится на 7», «цифры не повторяются», «нет двух одинаковых подряд»), жадность ломается: локально лучший выбор может закрыть путь к ответу, и приходится переходить к перебору с состоянием.

С чем путают. Соседний приём — динамика по цифрам: состояния вида «прошли i разрядов, набрали такую-то сумму, идём вплотную к границе или уже свободны». Внешне похоже, но отвечает она на другой вопрос — не «выдать одно число», а «посчитать, сколько чисел в диапазоне обладают свойством». Простое правило: спрашивают количество — жадность не подойдёт; просят конкретное число — динамика будет лишней работой.

Сложность приёма: $O(L)$ на ответ, где $L$ — число разрядов.

---

Задача 1 — CF ~1400 — «Given Length and Sum of Digits...»

Что дано

Даны длина m и сумма s. Нужно найти наименьшее и наибольшее неотрицательные целые числа, у которых ровно m цифр в десятичной записи и сумма цифр равна s. Числа записываются без ведущих нулей.

Формат ввода: одна строка с двумя целыми числами m и s ($1 \le m \le 100$, $0 \le s \le 900$).

Формат вывода: два числа через пробел — сначала минимальное, затем максимальное. Если подходящих чисел нет, вывести -1 -1.

Пример 1:

Ввод:
2 15

Вывод:
69 96

Пример 2:

Ввод:
3 0

Вывод:
-1 -1

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

Возьмём пример 1: m = 2, s = 15. Двузначных чисел с суммой цифр 15 немного: 69, 78, 87, 96. Наименьшее — 69, наибольшее — 96. Перебором это находится мгновенно, но при m = 100 перебирать нечего: чисел столько, что их не сосчитать, и в числовой тип такое число не помещается — сто цифр против девятнадцати у 64-битного целого.

Значит ответ надо не искать, а строить. Посмотрим, как получается 96 (максимум). Старший разряд определяет число сильнее всех остальных вместе взятых: любое число, начинающееся с 9, больше любого числа той же длины, начинающегося с 8. Поэтому в старший разряд жадно ставим максимум возможного — 9, при этом на последний разряд остаётся 15 − 9 = 6, и это допустимо (одна цифра вмещает от 0 до 9). Получилось 96.

Теперь 69 (минимум). Логика зеркальная: старший разряд надо сделать как можно меньше. Ноль туда нельзя — запрещены ведущие нули. Пробуем 1: тогда на последний разряд остаётся 14, а одна цифра больше 9 не вмещает — не выходит. Пробуем 2 — остаётся 13, снова много. И так до 6: остаётся 9, ровно помещается. Получаем 69.

Отсюда видно и общее правило для минимума: цифра старшего разряда — это наименьшее d, для которого одновременно d ≥ 1 и s − d ≤ 9 · (m − 1). Дальше ту же логику применяем к следующему разряду.

Идея решения

Алгоритм в одну фразу: сначала проверить достижимость s при длине m, затем собрать максимум жадно слева (каждый раз берём min(9, остаток)), а минимум — тоже слева, но беря наименьшую цифру, при которой остаток ещё помещается в оставшиеся разряды.

Почему это работает. Числа сравниваются посимвольно слева направо, поэтому старший разряд важнее всех последующих: увеличив старшую цифру на единицу, мы увеличиваем число сильнее, чем любое изменение всех младших разрядов. Значит для максимума первая цифра обязана быть максимально возможной; при фиксированной первой цифре та же логика применяется ко второй и так далее. Для максимума ограничение одно — не потратить больше, чем осталось: цифра min(9, остаток). Достижимость гарантируется тем, что оставшийся остаток всегда можно распределить (мы уже проверили s ≤ 9m).

Для минимума добавляется вторая проверка. Мало взять маленькую цифру — надо, чтобы остаток s − d не превысил вместимость хвоста, то есть 9 · (число оставшихся разрядов). Поэтому цифра старшего разряда — max(1, s − 9·(m−1)), а каждого следующего — max(0, остаток − 9·(число разрядов после текущего)).

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

Отдельно — случай s = 0. Сумма цифр ноль означает, что все цифры нулевые. Единственное такое число без ведущих нулей — 0, и его длина равна 1. Значит при m = 1 ответ 0 0, а при m > 1 подходящих чисел нет.

Псевдокод

прочитать m, s

если s == 0:
    если m == 1: вывести "0 0"
    иначе:       вывести "-1 -1"
    завершить

если s > 9 * m:
    вывести "-1 -1"      // даже все девятки не дают такую сумму
    завершить

// максимум: жадно слева направо
остаток = s
для i от 0 до m-1:
    hi[i] = min(9, остаток)
    остаток = остаток - hi[i]

// минимум: единица в старший разряд, девятки справа налево, излишек — в старший
lo = массив из m нулей
остаток = s - 1
для i от m-1 вниз до 1:
    lo[i] = min(9, остаток)
    остаток = остаток - lo[i]
lo[0] = 1 + остаток

вывести lo как строку, пробел, hi как строку

Код решения

Комментарии по реализации. Ответ хранится строкой (в Python — списком цифр, который склеивается при выводе): при m = 100 число из ста цифр не помещается ни в один встроенный целочисленный тип C++, и «собрать число, а потом напечатать» — тупик. Остаток в строке минимума после набивки девяток гарантированно не больше 8: если бы он был 9 или больше, эту девятку забрал бы предыдущий младший разряд. Поэтому lo[0] = 1 + rest всегда даёт корректную цифру от 1 до 9.

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

Пример 1: m = 2, s = 15. Достижимость: 9 · 2 = 18 ≥ 15 — ответ существует.

Наш вывод: 69 96 — совпадает с ожидаемым.

Пример 2: m = 3, s = 0. Срабатывает спецслучай s = 0 при m > 1: число из трёх цифр с нулевой суммой цифр — это 000, а такая запись запрещена ведущими нулями.

Наш вывод: -1 -1 — совпадает с ожидаемым.

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

• m = 1, s = 0. Ответ 0 0 — единственный случай, когда ноль в старшем разряде допустим (само число нулевое). Самая частая причина падения решения на этой задаче.
• m > 1, s = 0. Ответ -1 -1.
• s > 9m. Даже число из одних девяток не даёт такой суммы — -1 -1. Проверять до построения.
• s = 9m. И минимум, и максимум состоят из одних девяток и совпадают.
• m = 1, 1 ≤ s ≤ 9. Минимум и максимум равны s.
• m = 100, s = 900. Верхняя граница: сто девяток. Проверка на то, что ответ действительно строится строкой, а не числом.
• s = 1. Минимум и максимум — 1 и нули после него, то есть 10...0; жадность справа корректно оставляет всю единицу старшему разряду.

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

1. Хранить ответ в числовом типе. При m = 100 не хватит ни long long, ни unsigned long long. Ответ — строка или массив цифр от начала и до конца.
2. Забыть спецслучай s = 0. Решение «в старший разряд минимум 1» на s = 0 выдаёт -1 -1 даже при m = 1, хотя правильный ответ — 0 0.
3. Для минимума всегда ставить 1 в старший разряд. Работает только пока s − 1 ≤ 9·(m−1). Если сумма большая, а разрядов мало (как в примере с m = 2, s = 15), старшая цифра обязана быть больше единицы.
4. Проверять достижимость только сверху. Условие s ≤ 9m необходимо, но недостаточно: запрет ведущего нуля отсекает ещё и s = 0 при m > 1.
5. Строить минимум справа налево «жадно наименьшими цифрами». Наименьшая цифра в младших разрядах — это ноль, и тогда вся сумма уезжает в старший разряд, давая максимум вместо минимума. Девятки в минимуме прижимаются именно к младшим разрядам.
6. Печатать список цифр как есть (в Python — print(lo) вместо склейки в строку). Формально ошибка вывода, но ловится только на первом же тесте.

Сложность

Время: $O(m)$ — по одному проходу на минимум и на максимум. Память: $O(m)$ — две строки длины m.

---

Задача 2 — CF ~1500 — «Decrease the Sum of Digits»

Что дано

Дано целое число n. За один ход разрешается увеличить его на единицу. Нужно найти минимальное число ходов, после которых сумма цифр числа станет не больше заданного порога s.

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

• Строка 1: целое число t ($1 \le t \le 2 \cdot 10^4$) — количество тестов.
• Каждая из следующих t строк: два целых числа n и s ($1 \le n \le 10^{18}$; $1 \le s \le 162$).

Формат вывода: для каждого теста — минимальное число ходов.

Пример 1:

Ввод:
5
2 1
1 1
500 4
217871987498122 10
100000000000000001 1

Вывод:
8
0
500
2128012501878
899999999999999999

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

Возьмём третий тест: n = 500, s = 4. Сумма цифр равна 5 — на единицу больше порога. Первая мысль: прибавлять по единице и смотреть. 501 даёт сумму 6, 502 — семь, и дальше только хуже; на 510 сумма падает до 6, потом снова растёт. Видно главное свойство суммы цифр: она уменьшается только в моменты, когда какой-то разряд переполняется и обнуляется, а между переполнениями монотонно растёт.

Значит идти по единице бессмысленно — надо сразу прыгать в точку, где обнуляется хвост. Ближайшая такая точка — кратное 10; но 500 уже кратно 10, прыжка не происходит, сумма остаётся 5. Следующая — кратное 100, и снова 500. Следующая — кратное 1000, то есть 1000: сумма цифр 1, порог выдержан. Ответ 1000 − 500 = 500, ровно как в эталоне.

Второй тест напоминает про частный случай: n = 1, s = 1 — сумма цифр уже не превышает порог, ходов не нужно вовсе. Проверку исходного числа надо делать до входа в цикл, иначе решение честно прибавит лишнее.

Идея решения

Алгоритм в одну фразу: округлять n вверх до кратного 10, 100, 1000, … — до первого числа, у которого сумма цифр не больше s; ответ — разность с исходным числом.

Почему это работает. Это в точности рассуждение из теории, применённое к нашему свойству. Пусть m — минимальное число не меньше n с суммой цифр не больше s, и пусть m > n. Возьмём самый старший разряд, в котором m и n различаются: выше него цифры совпадают, а в нём цифра m строго больше. Построим число c: старшая часть — как у n, в этом разряде цифра n плюс единица, весь хвост ниже — нули. Тогда c больше n и не больше m. Сумма цифр c не больше суммы цифр m: старшая часть общая, цифра в разряде не увеличилась по сравнению с m, а нулевой хвост ничего не добавляет. Выходит, c тоже удовлетворяет условию — а раз m минимальное, то c = m.

Осталось заметить, что c — это ровно «n, округлённое вверх до кратного $10^k$», где $10^k$ — вес обнулённого хвоста. Кандидатов не больше 19 (столько знаков максимум у числа до $10^{18}$), и брать надо первый подошедший: с ростом k кандидат только растёт, значит первый подошедший и есть минимальный.

Почему цикл обязательно закончится. На последнем шаге n округляется до $10^{19}$ — числа с суммой цифр 1. По условию s не меньше единицы, так что этот кандидат подходит всегда.

Тонкость с уже круглым числом. Если n кратно $10^k$, округление его не меняет, и шаг проходит «вхолостую». Это правильное поведение: прибавлять целый $10^k$ только ради того, чтобы что-то изменилось, дороже, а сумму цифр это не улучшит. Именно так проходит третий тест, где 500 дважды остаётся собой, прежде чем прыгнуть в 1000.

Псевдокод

прочитать t

повторить t раз:
    прочитать n, s
    начало = n
    вес = 1
    пока сумма_цифр(n) > s:
        вес = вес * 10                  // обнуляем хвост на разряд длиннее
        остаток = n mod вес
        если остаток != 0:
            n = n + (вес - остаток)     // округление вверх до кратного «вес»
    вывести n - начало

Код решения

Комментарии по реализации. Главная ловушка в C++ — тип. Исходное n доходит до $10^{18}$ и помещается в знаковый long long (его предел ≈ $9{,}2 \cdot 10^{18}$), но последнее округление уводит число к $10^{19}$, и знаковый тип переполняется с неопределённым поведением. Поэтому и n, и power объявлены unsigned long long с пределом ≈ $1{,}8 \cdot 10^{19}$. В Python этой проблемы нет — целые там неограниченные, зато есть своя: сумма цифр пересчитывается на каждой итерации, поэтому она вынесена в дешёвую форму через str(n), а весь ввод читается одним куском — при $t = 2 \cdot 10^4$ построчный input() заметно медленнее.

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

Пример 1: пять тестов.

Наш вывод: 8 / 0 / 500 / 2128012501878 / 899999999999999999 — совпадает с ожидаемым по всем пяти тестам.

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

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

• Сумма цифр уже не больше s. Ответ 0, цикл не выполняется. Проверка обязана стоять до первого округления.
• n кратно степени десятки (500, 1000, $10^{18}$). Округление на соответствующем шаге ничего не меняет — это нормальный холостой шаг, а не ошибка в условии выхода.
• s = 162. Максимум суммы цифр для 18 девяток — как раз $18 \cdot 9 = 162$, так что порог никогда не нарушается и ответ всегда 0. Верхняя граница s выбрана в условии именно так.
• s = 1. Самый дорогой случай: подходят только числа вида $10^k$, и ответ может достигать почти $9 \cdot 10^{17}$.
• n = 10^18 (верхняя граница). Сумма цифр 1 — ответ 0 при любом s.
• n = 999999999999999999 (18 девяток, сумма 162). При s < 162 первое же округление даёт $10^{18}$ с суммой 1.
• $t = 2 \cdot 10^4$ тяжёлых тестов. На каждый тест не больше 19 итераций, то есть максимум порядка 400 тысяч пересчётов суммы цифр — с запасом укладывается.

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

1. Прибавлять по единице в цикле. Прямолинейное «пока сумма цифр велика, n += 1» верно по смыслу, но ответ доходит до $9 \cdot 10^{17}$ — программа не завершится никогда.
2. Знаковый long long в C++. На последнем округлении число уходит за $9{,}2 \cdot 10^{18}$, и знаковый тип переполняется. Нужен unsigned long long — или ранний выход, когда сумма цифр гарантированно мала.
3. Забыть проверить исходное число. Если сразу войти в цикл с округления, тест 1 1 выдаст 9 вместо 0.
4. Округлять «вниз». n - n % power даёт ближайшее круглое снизу, то есть число меньше n — по условию ходить назад нельзя.
5. Добавлять power даже когда остаток нулевой. Тогда 500 превратится в 600, потом в 1500 и так далее: ответ вырастет и перестанет быть минимальным.
6. Перебирать k только до 18. Ответ для n близких к $10^{18}$ требует округления до $10^{19}$ — на единицу больше, чем кажется по числу знаков.

Сложность

Время: $O(L^2)$ на тест в худшем случае, где $L \le 19$ — число разрядов (до 19 округлений, каждое с пересчётом суммы цифр за $O(L)$); фактически это меньше четырёхсот операций на тест. Память: $O(1)$.

---

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

Все четыре — на сегодняшний приём: ни в одной ответ не считается формулой, везде он собирается или правится по одному разряду.

• Codeforces 1157B «Long Number» (~CF 1300) — дано длинное число и таблица замен, задающая для каждой цифры её новое значение; разрешается выбрать один непрерывный отрезок цифр и заменить в нём все цифры по таблице — нужно получить максимально возможное число. Форма 1 в чистом виде: где начать отрезок и где его оборвать, решается на каждом разряде локально.
• Codeforces 537B «Quasi Binary» (~CF 1400) — представить число суммой наименьшего количества слагаемых, в записи которых встречаются только нули и единицы. Ответ читается прямо по разрядам, и его минимальность стоит попробовать доказать самому — рассуждение короткое.
• Codeforces 1181B «Split a Number» (~CF 1500) — разрезать десятичную запись числа на две части так, чтобы их сумма была минимальной. Число не помещается ни в один встроенный тип, поэтому складывать придётся столбиком по разрядам — ровно та ситуация из теории, где ответ живёт строкой.
• Codeforces 1932E «Final Countdown» (~CF 1600) — посчитать суммарное время обратного отсчёта, когда разряды табло переключаются независимо. Самая сложная в наборе: ответ набирается поразрядно, но с переносами, и именно на переносах чаще всего ломается первое решение.

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

---

Что дальше

Первая сессия «Плато» позади: один приём в двух формах — собрать число по разрядам и подправить его округлением вверх. Общее у них то, ради чего фаза и затевалась: ответ не ищут перебором, а строят, и каждый шаг обоснован, а не угадан. На следующей тренировке остаёмся в коридоре ~CF 1400–1500 и берём два указателя по отсортированному массиву — приём, который на «Плато» встречается едва ли не чаще всех остальных.