#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\), то — количество фигур, вырезанных из листа).

Примеры

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

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

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

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

#1111

Обход в глубину

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

Источники: [ Командные олимпиады, ВКОШП, 2008, Задача D ]

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

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

Паскаль

Си

var

a: array [1..maxn, 1..maxn] of boolean;

visited: array [1..maxn] of boolean;

procedure dfs(v: integer);

var

i: integer;

begin

writeln(v);

visited[v] := true;

for i := 1 to n do begin

if a[v][i] and not visited[i] then begin

dfs(i);

writeln(v);

end;

procedure graph_dfs;

var

i: integer;

begin

for i := 1 to n do

if not visited[i] then

dfs(i);

end;

int a[maxn + 1][maxn + 1];

int visited[maxn + 1];

void dfs(int v) {

printf("%d\n", v);

visited[v] = 1;

for (int i = 1; i <= n; i++) {

if ((a[v][i] != 0) && (visited[i] == 0)) {

dfs(i);

printf("%d\n", v);

}

void graph_dfs() {

for (int i = 1; i <= n; i++) {

if (visited[i] == 0) {

dfs(i);

}

Петина программа хранит граф с использованием матрицы смежности в массиве a (вершины графа пронумерованы от 1 до n). В массиве visited помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру graph_dfs для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

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

Первая строка входного файла содержит два целых числа: n и l количество вершин в графе и количество чисел в выведенной последовательности (1 ≤ n ≤ 300, 1 ≤ l ≤ 2n − 1). Следующие l строк по одному числу вывод Петиной программы. Гарантируется, что существует хотя бы один граф, запуск программы Пети на котором приводит к приведенному во входном файле выводу.

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

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

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

Примеры

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

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

#1203

Кенгуренок Лео

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

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2006, 2 тур, Задача B ]

#1355

Векторы

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

Источники: [ Личные олимпиады, Украинские олимпиады, 2004, 1 день, Задача A ]

На плоскости задано множество точек (x, y), где x, y – целые числа, 1≤x≤M, 1≤y≤N. Из каждой точки выходит ровно один из следующих векторов: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Каждый вектор соединяет одну целочисленную точку плоскости с другой. Например, если из точке (2, 5) выходит вектор (1, 1), то он соединяет эту точку с (3, 6), но не наоборот.

Последовательность из двух и более точек плоскости a₁, a₂,…, a_k назовем циклом, если каждая точка a_i соединена вектором с a_i₊₁ (1≤i≤k-1), и a_k соединена вектором с a₁. Циклы считаются разными если они отличаются хотя бы одной вершиной.

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

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

Первая строка входного файла содержит два целых числа N (1≤N≤100) и M (1≤M≤100). Каждая из последующих N строк, содержит M пар чисел (т.е. 2≤M чисел). Пара x, которая находится в строке y, задает вектор в точке (x, y).

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

Единственная строка выходного файла должна содержать целое число – количество циклов, образованных векторами.

Примеры

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

2 4 
-1 1 -1 1 -1 0 0 1
1 0 1 0 0 -1 0 -1

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