Собираем процессор
Задачу добавил: alef
Успешно сдано решений: 0
Конструктивными элементами процессора Кракатау являются квадратные блоки,
которые необходимо разместить на прямоугольной плате. Эти блоки соединяются
между собой специальными шинами. Нужно спроектировать оптимальную структуру
процессора: пересечений между шинами должно быть как можно меньше, при этом
суммарная длина шин должна быть минимальной (из возможных при данном
количестве пересечений)
Блоки и шины в силу технологических особенностей могут располагаться
только параллельно сторонам платы. (Шина может быть ломаной из нескольких отрезков,
при этом каждый отрезок параллелен одной из сторон платы)
Формат входного файла input.txt
Первая строка - пять целых чисел: N - количество квадратных блоков,
L - длина стороны каждого квадратного блока, D - минимальное расстояние
между квадратными блоками, P, Q - длины сторон прямоугольной платы
(0<=N,L,D,P,Q<=10)
Следующие N строк содержат информацию о соединениях между блоками
В каждой из строк J+1 (J=1, 2, ..., N) записано не более N-1 чисел
через пробел. Эти числа - номера блоков, с которыми должен быть
соединен блок J. Соединение между двумя любыми блоками может быть только одно,
дублирующие записи рассматривать не нужно.
Шины прикрепляются к краям блоков
Формат выходного файла output.txt
Целое число - количество пересечений шин и (через пробел) вещественное число
с точностью два знака после запятой - суммарная длина шин
Если блоки невозможно разместить на прямоугольной плате, вывести слово NO
Пример входного файла
4 2 1 5 5
2 4
3
4 2
1
Пример выходного файла
0 4.00