Тренировочная сессия 2: целочисленная арифметика без ошибок округления СЕССИЯ

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

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

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

Нормально, если сначала кажется, что тут решать нечего — само по себе решение действительно короткое. Интереснее то, почему именно такая формула работает и где она обычно ломается.

---

Теория

Целочисленный потолок — округление вверх без float. Иногда результат деления нужно округлить в большую сторону, а не просто отбросить дробную часть. Делать это через float опасно — из-за погрешности можно получить неверный ответ на одном из тестов.

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

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

Как решать:

• вместо ceil(a / b) через деление с плавающей точкой считаем (a + b - 1) // b;
• прибавка b - 1 «дотягивает» целочисленное деление вниз до следующего целого — но только когда деление было неточным;
• если деление было точным, прибавка ничего не меняет.

Например, (7 + 3 - 1) // 3 = 9 // 3 = 3 — ровно то, сколько плит по 3 метра нужно, чтобы покрыть 7 метров.

Где ошибаются: путают с обычным округлением вниз (a // b) там, где нужен запас — например, «сколько коробок нужно» всегда округляется вверх, даже если слово «вверх» в условии не произнесено явно.

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

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

• в условии — сложение или сравнение векторов/точек с нулём;
• на самом деле каждую координату (x, y) можно считать отдельно, без «геометрии».

Как решать: сложение векторов покомпонентно — сумма по x не зависит от суммы по y. Поэтому «сумма векторов равна нулю» — это просто два отдельных равенства: сумма всех x равна нулю и сумма всех y равна нулю.

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

---

Задача 1 — CF ~1000 — «Театральная площадь»

Что дано

Театральная площадь в вымышленном городе имеет прямоугольную форму размером $n \times m$ метров. К годовщине города решено вымостить площадь квадратными гранитными плитами со стороной $a$.

Разрешено покрыть плитами площадь, большую, чем сама площадь (плиты могут свисать за края) — лишь бы вся площадь была покрыта. Ломать плиты нельзя. Стороны плит должны быть параллельны сторонам площади.

Нужно найти наименьшее количество плит, которое для этого потребуется.

Формат ввода. Одна строка с тремя натуральными числами: $n$, $m$, $a$ ($1 \leq n, m, a \leq 10^9$).

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

Пример:

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

Площадь $6 \times 6$, плита $4 \times 4$.

Вдоль каждой стороны длиной 6 плита стороной 4 укладывается один раз полностью (закрывает от 0 до 4) и один раз частично (нужно закрыть от 4 до 6, а плита покрывает от 4 до 8 — с запасом, но это разрешено). Значит, вдоль каждой стороны нужно 2 плиты, а не 1 (одной не хватит: $4 < 6$) и не 3 (двух уже достаточно).

Итого по одной стороне — $\lceil 6/4 \rceil = 2$ плиты. Площадь двумерная, значит плиты укладываются сеткой: $2 \times 2 = 4$ плиты. Это и есть ответ.

Ключевое наблюдение: задача распадается на две независимые одномерные — сколько плит нужно вдоль стороны $n$, и сколько вдоль стороны $m$. Ответ — произведение этих двух чисел.

Идея решения

Вдоль одной стороны длиной $L$ плитами шириной $a$ нужно $\lceil L / a \rceil$ штук — округление вверх, потому что последняя частично покрытая плита всё равно ставится целиком (ломать нельзя, а не закрыть — нельзя тоже).

Ответ:

$$\text{ответ} = \left\lceil \frac{n}{a} \right\rceil \cdot \left\lceil \frac{m}{a} \right\rceil$$

Почему это верно, а не просто «разумное предположение». Оси $n$ и $m$ независимы: то, сколько плит нужно по горизонтали, не зависит от того, сколько нужно по вертикали — сетка складывается как декартово произведение одномерных решений. А минимальное число сегментов длины $a$, покрывающих отрезок длины $L$ (без разрывов, с разрешённым выходом за границу и без дробления сегментов) — это ровно $\lceil L/a \rceil$: меньшее число сегментов покроет самое большее $a \cdot \lfloor L/a \rfloor < L$ при нецелом делении, то есть не докроет отрезок; на одну больше — уже избыточно.

Целочисленный потолок без float. Считать ceil(n / a) через деление с плавающей точкой рискованно — при $n, a$ до $10^9$ округление float начинает давать неверный результат на некоторых значениях. Вместо этого используем целочисленный трюк:

$$\left\lceil \frac{L}{a} \right\rceil = \left\lfloor \frac{L + a - 1}{a} \right\rfloor$$

Это обычное целочисленное деление (округление вниз), но к числителю прибавлен запас $a - 1$, который «дотягивает» до следующего целого именно тогда, когда деление не было точным, и не меняет результат, когда было точным.

Псевдокод

прочитать n, m, a

k_n = (n + a - 1) // a   // сколько плит нужно вдоль стороны n
k_m = (m + a - 1) // a   // сколько плит вдоль стороны m

вывести k_n * k_m

Код решения

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

Совпадает с ожидаемым ответом 4.

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

1. Сторона делится нацело на a. Например, $n = 8$, $a = 4$: $(8 + 3) // 4 = 11 // 4 = 2$ — ровно $8/4$, лишняя плита не добавляется. Формула не «переокругляет» точные случаи.
2. a больше стороны. $n = 3$, $a = 10$: $(3 + 9) // 10 = 12 // 10 = 1$ — одна плита с большим запасом, что и требуется (плиту дробить нельзя, значит нужна хотя бы одна).
3. Максимальные значения. $n = m = a = 10^9$ даёт ответ $1$, но при $n = m = 10^9$, $a = 1$ ответ — $10^9 \times 10^9 = 10^{18}$, что не помещается в 32-битный int (переполнение на $10^9 \cdot 10^9$). Нужен 64-битный тип.

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

1. int вместо long long в C++. Ответ до $10^{18}$ — обычный int (до $\sim 2.1 \cdot 10^9$) переполняется мгновенно. В Python эта проблема отсутствует — целые неограниченной точности.
2. Деление через float/double. ceil(n / (double)a) даёт неверный ответ на некоторых крупных значениях из-за погрешности представления чисел с плавающей точкой — плата за удобство синтаксиса ceil() из <cmath> на самом деле дороже, чем кажется.
3. Забыли округлить вверх. Простое n / a (округление вниз) — недосчитает одну плиту ровно там, где деление не точное. Проверяется тестом с $n = 6$, $a = 4$: 6 / 4 = 1 (неверно) против (6 + 3) / 4 = 2 (верно).
4. Спутали, что нужно перемножить, а не сложить. Ответ — произведение $k_n \cdot k_m$ (это площадь сетки плит), а не сумма — частая невнимательность при беглом чтении условия.

Сложность

Время: $O(1)$. Память: $O(1)$.

---

Задача 2 — CF ~1000 — «Юный физик»

Что дано

Дано тело в пространстве, на которое действует $n$ сил. Каждая сила задаётся тремя целыми координатами вектора $(x_i, y_i, z_i)$. Нужно определить, находится ли тело в равновесии — то есть равна ли нулю сумма всех действующих на него сил (векторная сумма).

Формат ввода. Первая строка — целое число $n$ ($1 \leq n \leq 100$) — количество сил. Далее следуют $n$ строк, в каждой — три целых числа $x_i, y_i, z_i$ ($-100 \leq x_i, y_i, z_i \leq 100$) — компоненты соответствующего вектора силы.

Формат вывода. «YES», если тело находится в равновесии, иначе «NO».

Примеры:

Пример 1 — вход:

3
4 1 7
-2 4 -1
1 -5 -3

Ожидаемый выход: NO.

Пример 2 — вход:

3
3 -1 7
-5 2 -4
2 -1 -3

Ожидаемый выход: YES.

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

Первый пример: три вектора $(4, 1, 7)$, $(-2, 4, -1)$, $(1, -5, -3)$.

Складываем отдельно по каждой оси, а не как «геометрическую» сумму векторов:

• по оси $x$: $4 + (-2) + 1 = 3$
• по оси $y$: $1 + 4 + (-5) = 0$
• по оси $z$: $7 + (-1) + (-3) = 3$

Сумма по $x$ равна 3, не 0 — значит тело не в равновесии. Ответ — NO, что совпадает с ожидаемым.

Второй пример: $(3, -1, 7)$, $(-5, 2, -4)$, $(2, -1, -3)$.

• по оси $x$: $3 + (-5) + 2 = 0$
• по оси $y$: $-1 + 2 + (-1) = 0$
• по оси $z$: $7 + (-4) + (-3) = 0$

Все три суммы равны 0 — тело в равновесии, ответ YES. Тоже совпадает.

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

Идея решения

Заводим три накопителя — sum_x, sum_y, sum_z, изначально равные нулю. Читаем $n$ троек чисел, к каждому накопителю прибавляем соответствующую компоненту. В конце проверяем: все три суммы равны нулю — выводим YES, иначе — NO.

Почему это корректно, а не только «похоже на верно». Векторная сумма $\sum_i \vec{F_i}$ по определению покомпонентна: $x$-компонента суммы — это сумма всех $x$-компонент слагаемых, аналогично для $y$ и $z$ (сложение векторов в декартовых координатах линейно и покоординатно). Равенство векторной суммы нулевому вектору эквивалентно системе из трёх скалярных равенств $\sum x_i = 0$, $\sum y_i = 0$, $\sum z_i = 0$ одновременно. Значит, порядок сложения и любая «векторная» интерпретация здесь не нужны вовсе — задача полностью сводится к трём обычным целочисленным суммам.

Псевдокод

прочитать n
sum_x = 0, sum_y = 0, sum_z = 0

повторить n раз:
    прочитать x, y, z
    sum_x += x
    sum_y += y
    sum_z += z

если sum_x == 0 и sum_y == 0 и sum_z == 0:
    вывести "YES"
иначе:
    вывести "NO"

Код решения

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

Оба примера сходятся.

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

1. $n = 1$. Единственная сила — тело в равновесии, только если сама эта сила нулевой вектор $(0, 0, 0)$. Формула работает без изменений: суммы совпадают со значениями единственной строки.
2. Все нули. $n$ строк вида 0 0 0 — суммы по всем осям нулевые, ответ YES. Тривиально, но проверяется тестами.
3. Максимальные по модулю значения. $n = 100$, каждая компонента $\pm 100$ — максимальная сумма по модулю $100 \times 100 = 10^4$. В пределы int укладывается с огромным запасом, long long в C++ здесь избыточен, но не вреден (используем для единообразия и защиты от будущих правок ограничений).
4. Сумма даёт ноль «случайно» при ненулевых слагаемых. Например, компоненты $50, -30, -20$ по одной оси — сумма 0, хотя ни одно слагаемое не ноль. Код проверяет именно сумму, а не то, что все числа нулевые, поэтому такой случай обрабатывается корректно.

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

1. Проверка каждой строки на равенство нулю вместо суммы по столбцам. Частая путаница: считать, что тело в равновесии, если каждая отдельная сила нулевая. На самом деле равновесие — про сумму всех сил, а не про то, что каждая сила по отдельности нулевая.
2. Досрочный break при первой ненулевой сумме. Если прерывать чтение входных данных сразу, как только sum_x != 0, оставшиеся строки входа не будут считаны, и последующее чтение (если оно есть в программе) собьётся или тестирующая система не получит ожидаемого количества операций чтения. Дочитывать нужно всё до конца, даже если ответ уже ясен.
3. Сравнение с -0 или использование float для сумм. Если по ошибке взять float/double для накопителей (например, чтобы «на всякий случай»), сравнение sum == 0.0 менее надёжно из-за потенциальных ошибок округления при промежуточных операциях — хотя для целых входных данных это маловероятно, привычка держать суммы целыми числами убирает даже теоретический риск.
4. Перепутан порядок чтения x, y, z. Если считать координаты не в том порядке, что дан во входе (например, z, y, x), суммы посчитаются неверно для несимметричных тестов — на первый взгляд код «работает», но падает на скрытых тестах, где оси действительно различаются.

Сложность

Время: $O(n)$ — один проход по всем силам. Память: $O(1)$ (или $O(n)$, если данные прочитаны в массив целиком, как в решении на Python — не влияет на порядок сложности, но можно писать и потоково, накапливая суммы на лету без хранения всего массива).

---

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

Codeforces 58A «Chat room» (~CF 1000) — по данной строке определить, можно ли, удаляя из неё символы, получить слово «hello» (как подпоследовательность, не обязательно подряд идущую).

Codeforces 118A «String Task» (~CF 1000) — из строки убрать все гласные буквы, перед каждой оставшейся согласной вставить точку, и привести все буквы к нижнему регистру.

Codeforces 476A «Dreamoon and Stairs» (~CF 1000) — по лестнице из $n$ ступеней можно подниматься шагами по 1 или 2 ступени; нужно найти минимальное число шагов, которое кратно заданному $m$ (или определить, что это невозможно).

Codeforces 108A «Palindromic Times» (~CF 1000) — по времени в формате HH:MM найти ближайший следующий момент, когда цифры на табло читаются одинаково в обе стороны.

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

---

Что дальше

На следующей тренировке поднимаем сложность до ~CF 1000–1100 и добавляем первую жадность: сортировку по остаткам и обоснование того, почему жадный выбор порядка вообще работает.