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

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


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

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

Старт: 01.янв.2019 в 00:00:00
Финиш: 31.янв.2019 в 23:00:00
Осталось: 264:02:25
• Турнирная таблица

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

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

• F. Макс и поиск закусочных
• 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$$$. Все подбираемые отрезки ленты имеют одинаковую плотность размещения светодиодов, задаваемую количеством светодиодов $$$LM$$$ на одном метре. Любой отрезок светодиодной ленты содержит линии разреза, расположенные на ленте друг от друга на $$$P = 1000 / LM$$$ миллиметров, где 1000 целочисленно делится на $$$LM$$$, и имеет длину $$$LB = K * P$$$, где $$$K$$$ - число светодиодов. Участок между двумя соседними линиями разреза будем называть светодиодной долькой.

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

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

Первая строка содержит три целых числа $$$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$$$),уникальный номер отрезка и число диодов в этом отрезке соответственно.

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

В случае если выбраны два отрезка с разными номерами, то выводятся две тройки чисел на разных строках.

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

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

Сначала требуется выводить отрезок с меньшим номером.

В случае если выбран один отрезок и разрезан пополам, то выводятся две тройки чисел на разных строках.

На первой строке, через пробел выведите три целых числа - уникальный номер выбранного отрезка, признак необходимости отрезать (0 – не нужно, 1 – нужно, в данном случае 1) и число светодиодных долек в отрезанной части.

На второй строке, через пробел выведите три целых числа - уникальный номер выбранного отрезка, признак необходимости отрезать (0 – не нужно, 1 – нужно, в данном случае 0) и число светодиодных долек оставшейся части.

Гарантируется, что ответ всегда существует.

Примеры

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

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

www.contester.ru