|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
586. Квадрирование прямоугольника
|
| Статистика | Послать на проверку | Задачу добавил Кесарев Максим Андреевич |
|
На плоскости имеется прямоугольник размера 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 |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Учебные курсы / | Алгоритмы и структуры данных / | Сюда помещаем задачи из курсовиков! / |
| 586. | 583. Определения приращения | 588. Перемножение матриц | 816. Перестановки |
| время генерации 0.094 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |