06/04/2025 20:00:09

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2824. Коттеджный поселок

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Василий руководит строительством элитного коттеджного поселка, имеющего форму прямоугольника с противоположными углами в точках (0, 0) и ( $W$ , $H$ ). Василий собирается проложить несколько узких (настолько узких, что их ширина считается нулевой) внутренних проездов, которые разобьют весь поселок на участки прямоугольной формы с целочисленными сторонами. Каждый из участков должен быть огорожен высоким забором точно по периметру. Смежные участки огораживаются независимо друг от друга, то есть внутренние проезды между участками окружаются заборами с обеих сторон. Стороны участков, совпадающие с внешними границами поселка, также должны быть огорожены.

Василий уже договорился с поставщиком о поставке стройматериалов, поэтому общая длина заборов в поселке теперь должна в точности равняться $L$ . Помогите Василию нарисовать любой подходящий план поселка или определите, что сделать это невозможно.

В единственной строке ввода находятся три целых числа: длина поселка $W$ , ширина поселка $H$ ( $1 <= W,H <= 100$ ) и требуемая длина заборов $L$ ( $2H + 2W <= L <= 10^9$ ).

Если создать требуемый план поселка невозможно, выведите единственную строку, содержащую -1. Если создать план возможно, в первой строке выведите число $N$ – количество участков. Затем выведите $N$ строк, описывающих прямоугольные участки. Каждая строка должна содержать четыре целых числа – координаты противоположных углов участка в порядке: $x_1$ , $y_1$ , $x_2$ , $y_2$ ( $0<=x_1,x_2<=W$ , $0<=y_1,y_2<=H$ ). Прямоугольники должны полностью покрывать территорию поселка без наложений и пропусков, и их суммарный периметр должен равняться $L$ . Если существует несколько подходящих планов, выведите любой из них.

Пример ввода 1

4 2 20

Пример вывода 1

План для примера 1 изображен на рисунке.

Пример

Участки имеют периметры 6, 6 и 8 соответственно.

Пример ввода 2

4 2 99

Пример вывода 2

-1

Система оценки и описание подзадач

Подзадача 1 (15 баллов)

$H=1$ , остальные ограничения из условий задачи.

Подзадача 2 (30 баллов)

$H=2$ , остальные ограничения из условий задачи.

Необходимые подзадачи: 1

Подзадача 3 (55 баллов)

Ограничения из условий задачи.

Необходимые подзадачи: 1, 2

Баллы за каждую из подзадач начисляются только в случае, если все тесты для этой подзадачи успешно пройдены. По запросу сообщается о первой ошибке.

Хотя примеры ввода не соответствуют ограничениям подзадачи 1, ваше решение должно давать правильный ответ и на этих примерах для выполнения дальнейшего тестирования.