Language:

Remote Training on Programming

For authors:

About project

Hello, Guest! Login or register.

586. Квадрирование прямоугольника

Time Limit:	6 seconds
Memory Limit:	5000KB
Points:	10

View Problem Statistics

Submit

Problem added Undefined

На плоскости имеется прямоугольник размера X на Y. Так же имеется набор N квадратов со сторонами K_1, K_2, ... , K_N.
(X, Y, N, K_i - натуральные).

Введем на прямоугольнике декартовую систему координат так,что левый верхний угол имеет координаты (0, 0), а правый нижний - (X, Y).
Необходимо определить, существует ли такое подмножество квадратов из набора, что ими можно замостить прямоугольник полностью без наложений и кусков квадратов вне прямоугольника.
Помещать квадраты в прямоугольник можно только таким образом, чтобы стороны квадратов были параллельны сторонам прямоугольника, а углы квадратов находилсь в целочисленных точках.
Каждый квадрат можно использовать не более одного раза.

Входные данные
В первой строке входного файла через пробел находятся 3 целых числа X, Y, N (1 <= X,Y <= 500, 1 <= N <= 10).
В следующей строке находятся N целых чисел K_i (1 <= i <= N, 1 <= K_i <= 500).

Выходные данные
Если прямоугольник замостить нельзя, выведите -1.
Иначе - в первой строке выведите количество квадратов Z в искомом множестве.
В следующих Z строках выведите по три числа в каждой строке n, x, y,
где n - номер квадрата из входного файла, x, y - координаты левого верхнего угла данного квадрата.

Пример входных данных 1
3 2 4
2 2 1 1

Пример выходных данных 1
3
1 0 0
3 2 0
4 2 1

Пример входных данных 2
2 3 2
2 2

Пример выходных данных 2
-1

View Problem Statistics

Submit

Author/source:

Educational Courses /

Data Structures and Algorithms /

Place for problems from students' projects /

586.

588. Перемножение матриц

816. Перестановки

589. Последняя цифра чисел

We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. The art of tackling miniproblems with all our energy will sharpen our talents for the real problems. Donald E. Knuth.

time generating 0.094 sec.