Замощение прямоугольника одинаковыми листами за O(1) — задача «Хорошее начало» РАЗБОР

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

Что дано

Даны $n$ крыш. Каждая крыша — прямоугольник размера $w \times h$ с левым нижним углом в начале координат $(0, 0)$. На каждой крыше уже положены два листа покрытия размером $a \times b$ — они не пересекаются друг с другом и хотя бы частично попадают на крышу. Листы нельзя поворачивать (ориентация $a$ по оси X, $b$ по оси Y фиксирована).

Для каждой крыши нужно определить: можно ли добавить произвольное число таких же листов $a \times b$ (без поворотов, без взаимных пересечений, допускается выход листов за границы крыши) так, чтобы вся крыша оказалась полностью покрыта. Ответ — «Yes» или «No».

Ограничения

• $1 \leq n \leq 10^4$
• $1 \leq w, h, a, b \leq 10^9$
• Координаты левого нижнего угла каждого листа: $-a + 1 \leq x \leq w - 1$, $-b + 1 \leq y \leq h - 1$ (гарантируют хотя бы частичное пересечение листа с крышей).

Формат ввода

Первая строка — число крыш $n$. Далее для каждой крыши две строки: первая содержит четыре числа $w$, $h$, $a$, $b$; вторая — четыре числа $x_1$, $y_1$, $x_2$, $y_2$ (координаты левых нижних углов двух уже положенных листов).

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

Для каждой крыши вывести отдельной строкой Yes, если покрытие достижимо, или No иначе.

Примеры

Вход:

3
6 5 2 3
-1 -2 5 4
4 4 2 2
0 0 3 1
2 2 1 1
0 0 1 1

Вывод:

Yes
No
Yes

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

Первая крыша из примера:

6 5 2 3
-1 -2 5 4

$w = 6, h = 5, a = 2, b = 3$. Лист №1 в точке $(-1, -2)$, лист №2 в точке $(5, 4)$.

Лист №1 покрывает прямоугольник $[-1, 1) \times [-2, 1)$ — торчит снизу-слева, заходит на крышу в $[0, 1) \times [0, 1)$.

Лист №2 покрывает $[5, 7) \times [4, 7)$ — торчит сверху-справа.

Интуитивно: эти два листа «по диагонали», между ними есть большая непокрытая область. Можем ли мы её замостить одинаковыми листами $2 \times 3$ без поворотов?

Попробуем ставить листы «слева направо, снизу вверх» с шагом $(a, b) = (2, 3)$. Лист №1 стоит на $(-1, -2)$. Если мы шагнём вправо $(-1+2, -2) = (1, -2)$, потом $(3, -2)$, потом $(5, -2)$ — это столбец из $x \in \{-1, 1, 3, 5\}$. Лист №2 имеет $x = 5$ — попадает в нашу сетку! Значит по оси X листы сочетаются: $5 - (-1) = 6$, делится на $a = 2$.

А по оси Y? Лист №1 стоит в $y = -2$, шагаем вверх: $y \in \{-2, 1, 4\}$. Лист №2 имеет $y = 4$ — тоже попадает: $4 - (-2) = 6$, делится на $b = 3$. Значит можно мостить хоть по строкам, хоть по столбцам.

Ответ: Yes.

Вторая крыша:

4 4 2 2
0 0 3 1

Шаг $a = 2$, листы по X в $\{0, 2\}$. Лист №2 имеет $x = 3$ — не попадает: $3 - 0 = 3$, не делится на 2.

Шаг $b = 2$, листы по Y в $\{0, 2\}$. Лист №2 имеет $y = 1$ — не попадает: $1 - 0 = 1$, не делится на 2.

Ни по строкам, ни по столбцам замостить нельзя. Ответ: No.

Третья крыша:

2 2 1 1
0 0 1 1

$a = b = 1$ — каждая клетка отдельный «лист». $1 - 0 = 1$ делится на $1$. Yes.

---

Идея решения

Ключевое наблюдение: любое корректное замощение крыши листами одного размера без поворотов (с возможным выходом за границы) обязательно разбивается на регулярную сетку — листы выстраиваются либо строго по строкам (одинаковые $y$-координаты в пределах одной строки), либо строго по столбцам (одинаковые $x$).

Почему так?

Без ограничения общности допустим, что где-то два соседних листа стоят «в одной строке»: одинаковый $y$, $x$ отличаются на $a$. Тогда лист слева от второго прикладывается к первому справа впритык — другого способа нет, потому что листы не пересекаются и не поворачиваются. Значит вся эта строка заполняется листами с шагом $a$ по X.

А следующая строка? Она покрывает $y$-диапазон $[y_0 + b, y_0 + 2b)$. Лист из следующей строки должен касаться текущей строки (иначе между строками щель). Касание — сторона к стороне, значит все листы следующей строки выравнены по $y = y_0 + b$.

И дальше — всё тянется: вся крыша покрывается рядами с шагом $b$ по Y, внутри ряда — с шагом $a$ по X. При этом $x$-координаты всех листов одной строки отличаются на $a$, а листов между соседними строками — совпадают (или тоже смещены на $a$, но в рамках одной глобальной сетки).

Аналогично, если два соседних листа «в одном столбце» (одинаковый $x$) — замощение идёт по столбцам.

Вывод: в корректном замощении все листы лежат на узлах сетки $\{(x_0 + i \cdot a, y_0 + j \cdot b) : i, j \in \mathbb{Z}\}$ для некоторой стартовой точки $(x_0, y_0)$.

Что это значит для двух заданных листов

Если замощение идёт «по строкам» (значит все листы на разных $x$, но $y$ кратны $b$ от стартового), то оба заданных листа должны быть на одном горизонтальном уровне, то есть $y_1 = y_2$. Тогда $x$ отличаются на кратное $a$: $(x_2 - x_1) \bmod a = 0$.

Если «по столбцам» — наоборот: $x_1 = x_2$ и $(y_2 - y_1) \bmod b = 0$.

Но есть ещё общий случай. Если $x_1 \neq x_2$ и $y_1 \neq y_2$, то можно попробовать любое из двух — достаточно выполнения любого из условий:

• $x_1 \neq x_2$ и $(x_2 - x_1) \bmod a = 0$ — значит листы совместимы с замощением «по строкам», и они окажутся на разных $x$-координатах одной и той же строки (либо разных строк, но в одной сетке).
• $y_1 \neq y_2$ и $(y_2 - y_1) \bmod b = 0$ — аналогично для столбцов.

Если же $x_1 = x_2$, то они в одном столбце — работает только «по столбцам»: нужно $(y_2 - y_1) \bmod b = 0$. Но в этом случае «первое» условие ($x_1 \neq x_2$) ложно, поэтому проверка просто сводится ко второму.

Аналогично, если $y_1 = y_2$ — проверяется только первое условие.

Итоговая формула

Yes тогда и только тогда, когда выполнено хотя бы одно из:

• $x_1 \neq x_2 \; \land \; (x_2 - x_1) \bmod a = 0$;
• $y_1 \neq y_2 \; \land \; (y_2 - y_1) \bmod b = 0$.

Иначе — No.

---

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

читать n
повторить n раз:
    читать w, h, a, b
    читать x1, y1, x2, y2
    cols_ok = (x1 != x2) и ((x2 - x1) mod a == 0)
    rows_ok = (y1 != y2) и ((y2 - y1) mod b == 0)
    если cols_ok или rows_ok:
        вывести "Yes"
    иначе:
        вывести "No"

$O(1)$ на крышу. Всего $O(n)$.

---

Код решения

Переключи вкладку, чтобы посмотреть второй язык. В Python про переполнение int думать не надо — он неограниченной точности. В C++ обязателен long long: координаты до $10^9$, разность $x_2 - x_1$ — до $2 \cdot 10^9$, в int не помещается.

Переменные $w, h$ в решении не используются напрямую — размер крыши не влияет на условие замощения (интуиция: мы работаем с бесконечной сеткой и проверяем, попадают ли оба листа в одну сетку).

---

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

Входные данные:

3
6 5 2 3
-1 -2 5 4
4 4 2 2
0 0 3 1
2 2 1 1
0 0 1 1

Крыша 1

$w=6, h=5, a=2, b=3$, листы $(-1, -2)$ и $(5, 4)$.

• $x_1 = -1 \neq x_2 = 5$, $(5 - (-1)) \bmod 2 = 6 \bmod 2 = 0$. cols_ok = true.
• $y_1 = -2 \neq y_2 = 4$, $(4 - (-2)) \bmod 3 = 6 \bmod 3 = 0$. rows_ok = true.
• Ответ: Yes ✓

Крыша 2

$w=4, h=4, a=2, b=2$, листы $(0, 0)$ и $(3, 1)$.

• $x_1 = 0 \neq x_2 = 3$, $(3 - 0) \bmod 2 = 1 \neq 0$. cols_ok = false.
• $y_1 = 0 \neq y_2 = 1$, $(1 - 0) \bmod 2 = 1 \neq 0$. rows_ok = false.
• Ответ: No ✓

Крыша 3

$w=2, h=2, a=1, b=1$, листы $(0, 0)$ и $(1, 1)$.

• $(1 - 0) \bmod 1 = 0$. cols_ok = true (плюс $x_1 \neq x_2$).
• Ответ: Yes ✓

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

---

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

1. Листы в одном столбце ($x_1 = x_2$)

Тогда cols_ok сразу false (из-за $x_1 \neq x_2$ условия). Остаётся проверить rows_ok: $y_1 \neq y_2$ (всегда так, т.к. листы не пересекаются) и $(y_2 - y_1) \bmod b = 0$.

2. Листы в одной строке ($y_1 = y_2$)

Симметрично: rows_ok false, проверяется только cols_ok.

3. Отрицательные координаты

Листы могут стоять в $x = -a + 1$ и т.д. Модульная арифметика по отрицательным числам в Python работает корректно ((-3) % 2 == 1), в C++ нужно учесть, что % может вернуть отрицательное. Но в задаче $x_2 \geq x_1$ не гарантируется, поэтому $x_2 - x_1$ может быть отрицательным. Однако для проверки «делится на $a$» важен только остаток, и в C++ (-6) % 2 == 0 корректно — никаких проблем с отрицательными не возникает для нулевой проверки.

Но если вдруг решаешь на языке, где % по-другому работает, — используй abs(x2 - x1) % a == 0, это всегда корректно.

4. Максимальные значения

$w, h, a, b \leq 10^9$, координаты до $10^9$ по модулю. Разность координат — до $2 \cdot 10^9$, в int не помещается. Обязательно long long в C++.

5. $n = 10^4$ крыш

$10^4$ операций $O(1)$ — мгновенно. Никаких оптимизаций ввода-вывода сверх обычных не требуется.

---

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

1. Пропустить проверку $x_1 \neq x_2$ / $y_1 \neq y_2$. Если не добавить эту проверку, при $x_1 = x_2$ получишь cols_ok = true (так как $0 \bmod a = 0$), хотя по замощению «по строкам» два листа в одной точке невозможны. В таком случае правильно замостить только по столбцам — и rows_ok должна контролировать этот путь отдельно.

2. Попытаться использовать $w, h$. Возникает ощущение, что размер крыши влияет. На самом деле — нет: задача сведена к бесконечной сетке, а крыша просто вырезает из неё нужный кусок. Ответ зависит только от того, совместимы ли два данных листа с какой-то сеткой шага $(a, b)$.

3. int в C++. Разность координат — до $2 \cdot 10^9$. В 32-битном int переполнение.

4. Неверная реализация % для отрицательных. В Python % всегда неотрицателен, в C++ может быть отрицательным, но для проверки «равно 0» это не имеет значения. Проблема возникла бы только если сравнивать остаток с конкретным положительным числом — нам не нужно.

5. Попытка перебрать все возможные листы. Размер крыши до $10^9$ — перебор невозможен. Решение концептуальное, не симуляционное.

---

Сложность

• Время: $O(1)$ на крышу, $O(n)$ всего.
• Память: $O(1)$.

---

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

Похожие задачи — на конструктивные алгоритмы и регулярные замощения:

• Codeforces 1466C «Canine poetry» — конструктивное преобразование строки, ключ — увидеть инвариант.
• Codeforces 1399D «Binary String To Subsequences» — распределение 0/1 на подпоследовательности, жадное построение.
• Codeforces 1593B «Make it Divisible by 25» — математическая жадность + перебор случаев.
• acmp.ru задача 266 «Парикмахерская» — жадное распределение по слотам.

Общий мотив: увидеть, что «ответ существует тогда и только тогда, когда выполнено простое арифметическое условие». Чаще всего — делимость, остатки, порядок.

---

Итого

• Идея: любое корректное замощение идёт «по строкам» или «по столбцам» — листы образуют регулярную сетку.
• Условие: $(x_1 \neq x_2 \land (x_2 - x_1) \bmod a = 0)$ $\lor$ $(y_1 \neq y_2 \land (y_2 - y_1) \bmod b = 0)$.
• Сложность: $O(n)$.
• Ловушки: забыть проверку $x_1 \neq x_2$ / $y_1 \neq y_2$; int вместо long long в C++; попытаться использовать $w, h$ (они не нужны).