e-olymp 8376. Рамка

Задача

prb8376.gifРамка $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

Код

Решение

Рассмотрим три случая размещения плиток. Для примера возьмем входные данные c e-olymp — $5 × 6$.

Обратим внимание, что ширина плитки равна одному. 

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

Второй случай. На рисунке длина плитки равна двум. Тут по горизонтали плитки занимают всю длину без одного уголка. Это означает, что длина рамки минус один кратна длине плитки. Ширине ничего не остается как тоже «отдать» свою единицу. В результате, ширина рамки минус один тоже кратна длине плитки.

Третий случай. На рисунке длина плитки равна трём. Плитки укладываются тут не от края до края, а оставляя уголки рамки свободными. Так получаем, что длина рамки минус две единицы (уголки) кратна длине плитки. Ширина тоже кратна длине плитки, но только в полном размере.

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

Ссылки

Задача на e-olymp

Код задачи на Ideone