#999

Юный поджигатель

Темы: [Алгоритм Флойда] [Способы задания графа]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2004, 2 день, Задача C ]

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

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.

На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:

Спички длины 1 выкладывались по сторонам клеток.
Спички длины выкладывались по диагоналям клеток.

Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке, имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).

Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью). Спичка может гореть в нескольких местах (например, когда она загорается с двух концов; или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается по вновь подожженной спичке в обе стороны).

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

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

Во входном файле записано сначала число N — количество спичек (1N40). Затем идет N пятерок чисел вида X₁, Y₁, X₂, Y₂, T, задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или , все спички образуют связную фигуру, и положение никаких двух спичек не совпадает). Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее 10⁷.

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

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

Примеры

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

1
0 0 1 1 1

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

0 0
1.00

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

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

0 0
3.25

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

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

2 2
35.00

#1003

Вырезанные фигуры

Темы: [Обход в ширину] [Способы задания графа]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2004, 1 день, Задача C ]

Дано клетчатое поле и вырезанные на нем полосы (вертикальные или горизонтальные). Необходимо подсчитать, сколько фигур вырезано.

Эпидемия гриппа не обошла стороной семиклассника Алешу. Скучая дома, Алеша решил вырезать фигурки из листа клетчатой бумаги. Лист состоял из M строк и N столбцов клеточек. Сначала Алеша нарисовал на листе границы фигур. Количество фигур было не меньше 2. Чтобы фигуры получались ровными, границы фигур Алеша рисовал строго по линиям имеющейся клеточной разметки листа (при этом некоторые границы фигур могли пройти по границам листа). Форма фигур могла быть любой, но при этом все фигуры были связными (фигура называется связной, если из любой ее клетки можно добраться до любой другой, ходя только по клеткам фигуры и перемещаясь каждый раз в одну из 4-х соседних по стороне клеток). Никакие две фигуры не имели общих точек, в том числе не касались углами клеток.

<>Затем Алеша вырезал нарисованные фигуры, делая разрезы только по их границам. При этом оставшаяся часть листа осталась связной (то есть не распалась на несколько частей).

Лист с вырезами Алеша отсканировал. Сканер в своей памяти по результатам сканирования построил таблицу, состоящую из нулей и единиц, из M строк и N столбцов (строки нумеруются сверху вниз от 1 до M, столбцы — слева направо от 1 до N). Каждый элемент таблицы соответствовал клеточке исходного листа. Единица обозначала, что соответствующая клетка листа осталась на месте, ноль — соответствующая клетка была вырезана.

На рис. 1 приведен пример клетчатого листа, а на рис. 2 — соответствующая ему таблица в памяти сканера:

Рис 1.

Исходный клеточный лист с вырезанными фигурами

Размер листа: M=6, N=12.

Количество вырезанных фигур: 3

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

1

1

1

0

0

0

0

0

1

1

0

0

1

1

1

1

0

0

1

1

1

1

1

1

1

1

0

0

0

0

0

1

1

1

1

0

0

1

1

1

0

1

0

1

1

1

1

0

0

1

1

1

1

1

1

1

1

Рис 2.

Такая таблица строится в памяти сканера

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

Пункт 1. Сколько клеток было вырезано из листа?

Пункт 2. Сколько фигур было вырезано?

Описание формата представления таблицы

Последовательность подряд идущих по горизонтали или вертикали единиц будем называть полосой. Полосу можно задаеть 4 числами:

направление (0—горизонтальная, 1—вертикальная)

(i, j) — координаты начальной клетки полосы (начальной является самая левая клетка для горизонтальной полосы, и самая верхняя — для вертикальной), i — номер строки клетки, j — номер столбца

d — длина полосы (количество подряд стоящих единиц).>

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

В каждой клетке начинается не более одной полосы.
Полосы перечислены в порядке следования их начальных клеток (клетки перечисляются по строкам сверху вниз, в строке — слева направо).
Общее число полос не превышает 256000.

Заметим, что таблица может быть представлена в виде полос разными способами, но каждое представление позволяет однозначно восстановить таблицу.

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

Во входном файле записано сначала число \(P\) (1 или 2) — номер пункта задачи, ответ на который требуется получить. Далее записаны размеры исходного листа — числа \(M\) и \(N\) \((1 \le M \le 4000, 1 \le N \le 4000)\). Затем записано число \(K\) \((0 \le K \le 256000)\) — количество полос в описании полученной таблицы. Затем идет K четверок чисел, описывающих полосы (полосы перечисляются в порядке начальных клеток полос: по строкам сверху вниз, в строке — слева направо).

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

В выходной файл выведите искомое количество (если \(P=1\), то — количество клеток, вырезанных из листа, если \(P=2\), то — количество фигур, вырезанных из листа).

Примеры

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

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

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

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

#111508

Кружки в Маховниках

Темы: [Топологическая сортировка]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2013, Задача E ]

Маленький Петя очень любит компьютеры и хочет научиться программировать.

В небольшом городке Маховники, где он живёт, работает сеть кружков по программированию самой разной тематики. Когда Петя пошёл записываться, он увидел большой список, состоящий из N кружков. Петя хочет быть всесторонне развитой личностью, поэтому он собрался отучиться во всех этих кружках. Но когда он собрался записаться на все занятия сразу, обнаружилось, что не всё так просто. Во-первых, в один момент времени разрешается учиться только в одном из этих N кружков. Во-вторых, некоторые преподаватели выдвигают входные требования к знаниям учеников, заключающиеся в знании курсов каких-то других кружков!

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

Перед тем как сесть составлять порядок посещения кружков, Петя внимательно перечитал условия обучения и обнаружил ещё один важный пункт. Оказывается, для привлечения школьников, во всех кружках действует система поощрения учеников конфетами. Это означает, что по окончании очередного кружка ученику выдают несколько коробок конфет, всё больше и больше с каждым пройденным кружком. С другой стороны, в каждом кружке количество конфет в коробке своё, зависящее от сложности курса. Более конкретно — за прохождение i-го по счёту кружка, если этот кружок идёт в общем списке под номером j, ученику выдают аж N^i - 1·j конфет — такие щедрые люди программисты.

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

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

В первой строке входного файла содержится целое число N (1 ≤ N ≤ 100 000) — количество кружков в Маховниках.

В последующих N строках идут описания входных требований кружков, в порядке их следования в общем списке. В i-ой строке сначала записано целое число k_i (0 ≤ k_i ≤ N - 1) — количество кружков, в которых нужно отучиться перед записью в i-й кружок, а потом k_i номеров этих кружков.

Сумма k_i не превосходит 200 000.

Гарантируется, что возможно посетить все эти кружки в некотором порядке, не нарушая условия посещения.

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

Выведите N номеров, разделённых пробелами — порядок, в котором Пете надо посещать кружки, чтобы съесть как можно больше конфет.

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

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

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

2 1 3 5 4 6

Примечание

Пояснение к примеру. Посещая кружки в указанном порядке, Петя получит 6⁰·2 + 6¹·1 + 6²·3 + 6³·5 + 6⁴·4 + 6⁵·6 = 2 + 6 + 108 + 1080 + 5184 + 46656 = 53036 конфет.