Задача A. Конвертер графов ≡

Условие

Вам требуется написать программу, принимающую на вход ориентированный граф в заданном формате и выводящую этот же граф в заданном (возможно, другом) формате. Граф может содержать петли, но не содержит кратных ребер.

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

Первая строка входного файла содержит два слова. Первое — название формата графа во входном файле. Второе — название формата, в котором граф необходимо вывести.

Начиная со второй строки в файле содержится описание графа в одном из следующих форматов

• edges — список ребер. В этом случае первая строка описания графа должна содержать два целых числа N, M — количество вершин и количество ребер соответственно. Далее каждая следующая строка содержит два числа u и v — начало и конец очередного ребра.
• lists — списки смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее i-я строка (начиная со второй) содержит описание списка смежности (i−1)-й вершины. Первое целое число в строке c_i — количество вершин, в которые выходят ребра из (i−1)-й вершины. Далее через пробел следует c_i целых чисел — номера вершин, в которые выходят ребра из (i−1)-й.
• mat — матрица смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее следует N строк по N чисел 0 или 1 — описание матрицы смежности. Если в i-й строке на j-й позиции находится единичка, значит в графе есть ребро из (i−1)-й вершины в j-ю.

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

Выходной файл должен содержать описание графа в требуемом формате.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N²

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

edges mat
3 4
1 2
2 3
1 3
2 2

3
0 1 1
0 1 1
0 0 0

mat lists
4
1 0 1 1
0 0 0 0
1 1 0 0
0 1 1 0

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

Задача B. Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

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

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

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

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

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

Ограничения

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

3 1
2 3

2

Задача C. КПК ≡

Условие

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

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

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

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

Ограничения

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

3 1
2 3

1
2 3
1
1 2

Problem D. Topological sorting ≡

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number −1.

Constraints

Sample tests

4 3
1 2
1 3
3 4

1 3 2 4

Задача E. Производство деталей ≡

Условие

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p_i секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

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

Система оценивания

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

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

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂… p_n, определяющих время изготовления каждой детали в секундах.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей k_i, которые требуются для производства детали с номером i, а также их номера.

Известно, что не существует циклических зависимостей в производстве деталей.

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

В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Ограничения

1 ≤ n ≤ 100000, 1 ≤ p_i ≤ 10⁹

Сумма всех чисел k_i не превосходит 200000.

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

3
100 200 300
1 2
0
2 2 1

300 2
2 1

2
2 3
1 2
0

5 2
2 1

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

9 3
3 2 1

Задача F. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

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

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Задача G. Breadth First Search ≡

Условие

Требуется написать программу, которая получает невзвешенный неориентированный граф и выводит все его вершины в порядке увеличения расстояния от данной вершины S. Расстояние между вершинами A и B это длина кратчайшего пути из A в B. Если есть несколько вершин, находящихся на одном и том же расстоянии от вершины S, выведите их в произвольном порядке.

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

Входной файл содержит три целых числа N, M и S, где M — число рёбер, S — номер стартовой вершины. Вершины пронумерованы целыми числами от 1 до N. Каждая из следующих M строк содержит пару целых чисел — номера вершин, соединённых ребром.

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

Выходной файл должен содержать последовательность из N номеров вершин, упорядоченных по возрастанию расстояния от S. Если какая-то из вершин недостижима из S, выведите единственное число −1.

Ограничения

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

3 2 1
1 2
2 3

1 2 3

Задача H. Лабиринт ≡

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

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

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

В выходном файле должно содержаться единственное число — минимальное расстояние. Лабиринт проходим.

Ограничения

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

4 1 1 4 1
..#.
..#.
..#.
....

9

Problem I. Dijkstra ≡

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Задача J. Быстрый Дейкстра ≡

Условие

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

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

Ограничения

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

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Problem K. Ford-Bellman ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3 1
1 2 5
1 3 10
2 3 2

0 5 7

Problem L. Floyd-Warshall ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 5
1 3 10
2 3 2

0 5 7
  0 2
    0

Задача M. Светофоры ≡

Условие

Студент Вася каждый день ездит на машине в университет учиться. Система дорог города, в котором живет Вася, представляет собой на карте прямоугольную сетку состоящую из N × M перекрестков. Дом, от которого отъезжает Вася, находится в левом верхнем углу карты, а университет — в правом нижнем углу.

Все перекрёстки снабжены светофорами, работающими в необычном режиме. По всем направлениям перекрёстка одновременно горит либо зелёный, либо красный свет.

Вася уже давно ездит по этим дорогам и для каждого светофора знает все промежутки времени, когда он светит красным.

Итак, Васе нужно успеть на первую пару! Но Вася — порядочный гражданин и не станет проезжать на красный свет. В то же время, скорость автомобиля и состояние дорог в городе позволяют ему перемещаться между светофорами настолько быстро, что временем перемещения можно пренебречь. (Т. е. время проезда между перекрёстками равно нулю).

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

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

Входной файл содержит 2 целых числа N M.

Далее следует N × M расписаний светофоров, перечисленных в порядке обхода карты построчно. Первое число i−го расписания c_i — количество временных отрезков i−го светофора, за которым следует c_i пар целых чисел  — временные отрезки, когда i−ый светофор светит красным. Отрезки не пересекаются и отсортированы по возрастанию левой границы.

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

Выходной файл должен содержать единственное целое число — момент времени, когда Вася приедет в университет.

Ограничения

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

2 2
1 0 1
1 0 1
1 0 1
1 0 1

1

2 3
2 0 1 4 10
2 0 3 4 10
2 0 1 3 10
1 0 100
1 0 100   
1 0 100 

10

Задача N. Матрёшки АТЭС ≡

Условие

К моменту проведения саммита АТЭС во Владивостоке было решено изготовить подарочные наборы матрёшек, по N штук в каждом.

Матрёшек в каждом наборе располагают в порядке убывания вместимости и нумеруют от 1 до N. Таким образом самая большая матрёшка получает номер 1, а самая маленькая — N. Для упаковки матрёшек в набор используют следующий алгоритм: за один шаг каждая матрёшка, находящаяся на четной позиции, помещается (вместе со всеми матрёшками внутри) внутрь ближайшей слева матрёшки. Эта операция продолжается до тех пор, пока все матрёшки не будут упакованы в одну.

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

i-ый шаг алгоритма описывается путём указания четырёх чисел X_Li, X_Ri, Y_Li, Y_Ri, обозначающих, что после упаковки матрёшки с номером X_Ri в матрёшку с номером X_Li, матрёшка X оказалась внутри X_Li. Аналогично для матрёшки Y.

Последний шаг алгоритма описывается двумя числами L_F, R_F — после упаковки матрёшки с номером R_F в матрёшку с номером L_F оказалось, что матрёшки X и Y находятся внутри матрёшки L_F.

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

Входной файл содержит три целых числа — N X Y.

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

Выходной файл должен содержать подробный процесс упаковки матрёшек:

• Каждая строка, описывающая один шаг алгоритма, кроме последней, должна содержать четыре целых числа — X_Li, X_Ri, Y_Li, Y_Ri
• Последняя строчка должна содержать два целых числа — L_F, R_F

В случае, когда на каком-либо шаге в матрёшку ничего не упаковывается, указать, что матрёшка помещается сама в себя.

Ограничения

2 ≤ N ≤ 2³⁰

1 ≤ X < Y ≤ N

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

6 2 5

1 2  5 6
1 3  5 5
1 5

21 9 15

9 10  15 16
9 11  13 15
9 13

Problem O. SST for sparse graph ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 10
2 3 10
3 1 10

20

Задача P. Lode Runner возвращается ≡

Условие

Компания-разработчик компьютерных игр решила выпустить обновлённую версии классической аркадной игры Lode Runner.

Игра проходит в лабиринте, состоящем из горизонтальных платформ, соединённых лестницами. Лабиринт изображается в виде поля шириной W и высотой H клеток, каждая клетка которого содержит один из символов "." (ASCII 46) — свободное место, "X" (ASCII 88) — платформа и "#" (ASCII 35) — лестница.

По правилам игры, все платформы должны быть строго горизонтальными и не соприкасаться друг с другом (т.е. два символа "X" могут соседствовать только по горизонтали). Каждая лестница должна быть строго вертикальной и соединять две платформы (т.е. представлять собой вертикальную полосу из символов "#", над верхним и под нижним символом которой находятся символы "X"). Лестницы могут соприкасаться друг с другом, находясь на соседних вертикалях.

Из каждого символа платформы должна быть возможность перейти к любому другому символу, двигаясь только по платформам по горизонтали и лестницам по вертикали. Таким образом, непосредственное перемещение с одной лестницы на другую, а также между платформой и соседней по горизонтали лестницей невозможно.

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

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

Требуется написать программу которая по данному описанию уровня игры строит уровень, соответствующий правилам и получающийся из данного минимально возможным количеством замен символов "." и "#" друг на друга.

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

Первая строка входного файла содержит целые числа W H. Следующие H строк содержат по W символов каждая — описание уровня.

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

Выходной файл должен содержать H строк по W символов каждая — исправленное описание уровня. Если оптимальных решений несколько, выведите любое из них. Гарантируется, что хотя бы одно решение существует.

Ограничения

1 ≤ W, H ≤ 1000

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

6 4
.XX.X.
......
#.#...
XXXXX.

.XX.X.
..#.#.
..#.#.
XXXXX.