Задача
Рамка $x × y$ представляет собой прямоугольник $x × y$, из середины которого вырезали прямоугольник размером $(x — 2) × (y — 2)$. У нас имеется неограниченный запас плиток $a × 1$. Можно ли полностью замостить рамку $x × y$ плитками $a × 1$?
Например, рамку $5 × 6$ можно замостить плитками $3 × 1$, но нельзя плитками $4 × 1$.
Входные данные
Первая строка содержит два натуральных числа $x$ и $y (3 ≤ x, y ≤ 10^6)$. Вторая строка содержит количество типов плиток $n (1 ≤ n ≤ 1000)$. Третья строка содержит n натуральных чисел, не больших $10^6$ — длины плиток.
Выходные данные
Выведите n строк, содержащих YES или NO. i-ая строка содержит YES если можно замостить рамку плитками i-го типа. Выведите NO иначе.
Тесты
| № | Ввод | Вывод |
| 1 | 5 6 2 3 4 |
YES
NO |
| 2 | 18 5 2 6 3 |
NO
YES |
| 3 | 3 3 1 1 |
YES |
| 4 | 200 4 3 2 3 4 |
YES
NO NO |
| 5 | 1000000 1000000 5 100000 2 1689 11 9004 |
NO
YES NO YES NO |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; int main() { long long x, y, n, a; cin >> x >> y >> n; while (n--) { cin >> a; if ((a == 2) || (x % a == 0 && (y - 2) % a == 0) || ((x - 1) % a == 0 && (y - 1) % a == 0) || ((x - 2) % a == 0 && y % a == 0)) cout << "YES" << "\n"; else cout << "NO" << "\n"; } return 0; } |
Решение
Рассмотрим три случая размещения плиток. Для примера возьмем входные данные c e-olymp — $5 × 6$.
Обратим внимание, что ширина плитки равна одному. 
Первый случай. На рисунке изображен самый простой пример, когда длина плитки равна одному. Плитки по горизонтали идеально вписываются в размеры рамки. Это значит, что длина рамки кратна длине плитки. Если снизу и сверху рамку уложить плитками, то ширина рамки уменьшится, в связи с тем, что углы являются общими для ширины и длины. Получаем, что для того чтобы уложить остаток рамки плитками, длина плитки должна быть ещё и делителем ширины рамки, уменьшенной на две единицы.
Второй случай. На рисунке длина плитки равна двум. Тут по горизонтали плитки занимают всю длину без одного уголка. Это означает, что длина рамки минус один кратна длине плитки. Ширине ничего не остается как тоже «отдать» свою единицу. В результате, ширина рамки минус один тоже кратна длине плитки.
Третий случай. На рисунке длина плитки равна трём. Плитки укладываются тут не от края до края, а оставляя уголки рамки свободными. Так получаем, что длина рамки минус две единицы (уголки) кратна длине плитки. Ширина тоже кратна длине плитки, но только в полном размере.
Заметим, что если длина плитки будет равна двум, из таких плиток можно сложить рамку любых размеров. Этот случай вынесем отдельно.
One thought on “e-olymp 8376. Рамка”