ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Тренировочный турнир сезона «Зима — 2019» > задача:


P3. Подбор кусков ленты для квадратных пластин

Тренировочный турнир сезона «Зима — 2019»

Старт: 01.янв.2019 в 00:00:00
Финиш: 31.янв.2019 в 23:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (5)

Задачи турнира

• G. Макс и нестандартная спираль
• H. Макс и новогодние открытки
• I. Макс и распознавание фигур
• J. Макс и муниципальная задача
• K. СириусЛяндия и страсть к оливкам
• P1. Подбор отрезков ленты для од...
• P10. Бегущие огни в диагоналях
• P2. Подбор отрезков ленты для дв...
• P3. Подбор кусков ленты для ...
• P4. Бегущий огонь слева направо в...
• P5. Бегущий огонь справа налево в...
• P6. Бегущие пары слева направо в...
• P7. Бегущие пары справа налево в...
• P8. Бегущие колонки слева напра...
• P9. Бегущие колонки справа нале...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Подбор кусков ленты для квадратных пластин
Подбор кусков ленты для квадратных пластин
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Даниилу поручили разработать программу подбора отрезков светодиодной ленты для наклейки на квадратную алюминиевую пластину с длиной и шириной равной $$$LA$$$ (то есть пластина состоит из $$$LA$$$ независимых рядов каждый из которых имеет длину $$$LA$$$). Все подбираемые отрезки ленты имеют одинаковую плотность размещения светодиодов, задаваемую количеством светодиодов $$$LM$$$ на одном метре. Любой отрезок светодиодной ленты содержит линии разреза, расположенные на ленте друг от друга на $$$P = 1000 / LM$$$ миллиметров, где 1000 целочисленно делится на $$$LM$$$, и имеет длину $$$LB = K * P$$$, где $$$K$$$ - число светодиодов. Участок между двумя соседними линиями разреза будем называть светодиодной долькой.

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

Ваша задача построить светодиодный квадрат, то есть выбрать $$$K$$$ лент (возможно путём отрезания от других) таких, что их длина (в дольках) будет равна их количеству, то есть $$$K$$$. Если есть несколько вариантов построения сначала минимизируйте номер первой ленты, потом второй и так далее.

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

Первая строка содержит три целых числа $$$LM$$$, $$$LA$$$, $$$N$$$ ($$$1 \le LM \le 1000$$$, $$$100 \le LA \le 1000$$$, $$$5 \le N \le 99$$$)

Каждая из следующих $$$N$$$ строках содержит два числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i \le 99$$$, $$$1 \le b_i \le 99$$$), уникальный номер отрезка и число диодов в этом отрезке соответственно.

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

В первой строке выведите одно целое число $$$K$$$ — количество лент. В следующих $$$K$$$ строках выведите по 3 целых числа: уникальный номер ленты, признак необходимости отрезать (0 — если лента взята целиком, 1 — если лента подвергалась разрезу) и число светодиодных долек в отрезке. Третье число одинаково для всех лент.

Примеры

Входные данные
25 140 5
3 6
4 8
7 4
8 8
11 12
Выходные данные
3
3 1 3
3 1 3
4 1 3
Входные данные
50 140 5
3 6
4 8
7 4
8 4
11 12
Выходные данные
4
3 1 4
4 1 4
4 1 4
7 0 4

Для отправки решений необходимо выполнить вход.

www.contester.ru