Problem A. Distinct colors ≡

Statement

Colors on computer screen are represented by (r, g, b) triplets, where r, g, b are integer intensities of red, green and blue components.

Two colors (r₁, g₁, b₁) and (r₂, g₂, b₂) are distinct if min(|r₁ − r₂|, |g₁ − g₂|, |b₁ − b₂|) ≥ D.

Your program will be given N (not necessarily distinct) colors. It must either calculate K new colors that are distinct from each other and from all initial colors, or determine that it is impossible.

Input file format

Output file format

Constraints

Sample tests

2 1 10
255 100 100
100 100 255

110 110 110

2 1 200
255 100 100
100 100 255

-1

Задача B. Рейтинг студента ≡

Условие

Многие вузы переходят на рейтинговую систему оценки: оценки студентов зависят от того, как они сдают задания в течение всего семестра. Для каждого задания устанавливается срок сдачи, позже которого задание не принимается.

Один студент получил N заданий утром дня с номером 1.

• Студенту потребуется ровно L_i дней, чтобы выполнить задание с номером i.
• Если студент берётся за какое-либо задание, то он ни на что не будет отвлекаться, пока его не выполнит.
• Начав работать над заданием в день с номером x, студент закончит и сдаст его в день с номером x + L_i − 1. Силы взяться за новое задание будут у него только на следующий день.
• Задание с номером i не будет принято, если оно будет сдано позже, чем в день с номером D_i.
• Рейтинг студента увеличится на R_i баллов после сдачи задания с номером i.

Студент хочет, чтобы его рейтинг стал как можно выше. Напишите программу, которая, получив информацию о заданиях, определит, какие задания и в каком порядке должен выполнять студент, чтобы максимально повысить свой рейтинг.

Рекомендуется рассмотреть частичные решения

• N ≤ 2
• L₁ = L₂ = … = L_N = 1
• D₁ = D₂ = … = D_N

Формат входного файла

Входной файл содержит целое число N, за которым следует N троек целых чисел L_i D_i R_i — информация о заданиях.

Формат выходного файла

Программа должна вывести в выходной файл максимальное количество баллов, которое может заработать студент, а затем — описания заданий, которые ему нужно для этого выполнить. Каждое описание состоит из чисел k_i s_i — порядкового номера задания и номера дня, когда студенту нужно начать его выполнение. Все k_i должны быть различны. Задания должны быть выведены в порядке возрастания s_i.

Если студент не сможет заработать ни одного балла, вывести единственное число 0.

Если существует несколько способов заработать максимальное количество баллов, вывести любой из них.

Ограничения

1 ≤ N ≤ 1000; 1 ≤ L_i, D_i, R_i ≤ 1000

Примеры тестов

5
7 8 6
2 2 1
5 8 4
3 9 3
2 5 1

7
3 1
4 6

Задача C. Дорожная реформа ≡

Условие

Как известно, Флатландское государство состоит из n городов, которые соединены системой двусторонних железнодорожных путей и автомобильных шоссе.

Недавно, после очередной поездки по стране, президент Флатландии остался крайне недовольным состоянием дорог и сделал вывод о необходимости радикальных реформ системы путей и сообщений.

Так как дорог в государстве за долгие годы было построено много, и почти все они нуждались в капитальном ремонте, то комиссией было решено, что необходимо закрыть часть существующих дорог, а на восстановление оставшихся выделить деньги из бюджета. При этом, так как средств в бюджете крайне не хватало, то было решено оставить как можно меньше железных и автомобильных дорог, лишь бы только по ним можно было добраться из любого города государства в любой другой (возможно через промежуточные города, используя несколько железных и/или автомобильных дорог), а именно, решено было оставить и отремонтировать ровно n − 1 дорогу.

После изучения результатов работы комиссии правительство решило выделить деньги на ремонт a автомобильных и b железных дорог. Но перед ним встала непростая задача: какие же конкретно дороги следует закрыть, а какие — оставить и отремонтировать, чтобы все города государства остались связанными друг с другом?

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

Формат входного файла

В первой строке входного файла записано четыре целых числа: n — количество городов Флатландии, m — количество существующих автомобильных и железных дорог, a и b — количество автомобильных и железных дорог, которые необходимо оставить. Следующие m строк описывают имеющиеся дороги. Каждая из них содержит по три целых числа: u_i, v_i — номера городов, которые соединяет i-я дорога, и t_i — тип дороги, который равен 0 для автомобильной дороги, и 1 для железной.

Гарантируется, что ни один город не связан дорогой сам с собой, и что каждая пара городов соединена максимум одной автомобильной и одной железной дорогой. Также гарантируется, что перед реформой из каждого города можно добраться до каждого.

Формат выходного файла

Ограничения

Примеры тестов

4 4 1 2
1 2 1
1 3 0
2 3 1
3 4 1

1 2 4

3 2 2 0
1 2 1
2 3 0

Impossible