003. Рамка из клеток

(Время: 1 сек. Память: 16 Мб)

Прямоугольник состоит из X×Y квадратных клеток одинакового размера. Из него вырезан прямоугольник размером (X-2)×(Y-2) так, что осталась рамка шириной в одну клетку. Определить, можно ли покрыть всю рамку плитками размером A×1. Запас плиток неограничен, плитки не накладываются одна на другую и за пределы рамки не выходят.

Требуется написать программу, которая решает эту задачу.

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

Входной текстовый файл input.txt содержит в первой строке натуральное число K  количество тестов (1 ≤ K ≤ 10). В следующих K строках записаны по три натуральных числа: X, Y – размеры рамки, А – размер плитки (3 ≤ X, Y ≤ 2×109, 1 ≤ A ≤ 2×109). Числа разделены пробелами.

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

Выходной текстовый файл output.txt должен содержать одну строку из K символов 0 или 1 (1 – если покрытие существует, 0 – иначе).

Примеры

input.txt

output.txt

1

1

3 3 1

1

2

2

3 3 2

3 3 3

10

Информация о задаче

Автор, источник

Порублев И.Н., Ставровский А.Б. Алгоритмы и программы. Решение олимпиадных задач. – М.: Вильямс, 2007. – 480 с.

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2007-2008 уч. год, 1-й тур

Тематика

Простая математика

Примерная сложность

33%

Ссылки в Интернете

Условие, сдача решенияhttp://acmu.ru/index.asp?main=task&id_task=310

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор – А.В. Алексеев, дата – 11.01.2012

 

Разбор

Рамку можно покрыть плитками А×1, если А=1 или А=2 или одна из сторон кратна А, а вторая при делении на А дает остаток 2, или каждая при делении на А дает остаток 1.

Программа на Паскале

{Author - A.Alexeyev, Date - 11.01.2012}

var

  k : integer;

  x, y, a : longint;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(k);

  while k>0 do begin k:=k-1;

    readln(x,y,a);

    if (a<3) or (x mod a=0) and (y mod a=2) or

       (x mod a=2) and (y mod a=0) or

       (x mod a=1) and (y mod a=1) then write(1) else write(0)

  end

end.