Задача A. Максимальный поток (несколько истоков и стоков)

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Требуется найти максимальный поток в сети с несколькими истоками и стоками.

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

В первой строке входного файла содержится число N  — количество вершин в сети. Далее следует N чисел ai ∈ 0, 1, 2. Если ai = 0, то i-ая вершина  — это обычный узел; если ai = 1 то i-ая вершина  — это исток; если ai = 2 то i-ая вершина  — это сток. Гарантируется, что в сети есть хотя бы один исток и хотя бы один сток.

Далее следует матрица целых чисел U размером N × N. 0 ≤ Uij ≤ 106  — вместимость ребра из i-ой вершины в j-ую. На диагонали матрицы находятся нули.

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

В выходной файл выведите единственное число  — объем максимального потока.

Ограничения

2 ≤ N ≤ 50

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
0 100
1000 0
100
2
4
1 0 0 2
0 2 1 0
0 0 1 2
0 1 0 1
0 0 0 0
3
3
10
0 0 1 0 1 2 2 0 2 0 
0 100 0 0 0 1 0 0 0 0
0 0 0 0 0 120 0 0 0 0
100 0 0 0 0 0 0 0 0 0
10 10 0 0 0 0 0 20 0 20
0 0 0 50 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 15 0 15 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 10 0 0
141

Задача B. Min-cost-max-flow aka В поисках невест

Автор:Жюри летних сборов 2004   Ограничение времени:2 сек
Входной файл:brides.in   Ограничение памяти:64 Мб
Выходной файл:brides.out  

Условие

Однажды король Флатландии решил отправить k своих сыновей на поиски невест. Всем известно, что во Флатландии n городов, некоторые из которых соединены дорогами. Король живет в столице, которая имеет номер 1, а город с номером n знаменит своими невестами.

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

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

В первой строке входного файла находятся числа n, m и k — количество городов и дорог во Флатландии и сыновей короля, соответственно (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ k ≤ 100). Следующие m строк содержат по три целых положительных числа каждая — города, которые соединяет соответствующая дорога и время, которое требуется для ее прохождения (время не превышает 106). По дороге можно перемещаться в любом из двух направлений, два города могут быть соединены несколькими дорогами.

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

Если выполнить повеление короля невозможно, выведите на первой строке число 1. В противном случае выведите на первой строке минимальное возможное среднее время (с точностью 5 знаков после десятичной точки), которое требуется сыновьям, чтобы добраться до города назначения, не менее чем с пятью знаками после десятичной точки. В следующих k строках выведите пути сыновей, сначала число дорог в пути и затем номера дорог в пути в том порядке, в котором их следует проходить. Дороги нумеруются, начиная с единицы, в том порядке, в котором они заданы во входном файле.

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

Входной файл (brides.in) Выходной файл (brides.out)
1
5 8 2
1 2 1
1 3 1
1 4 3
2 5 5
2 3 1
3 5 1
3 4 1
5 4 1
3.00000
3 1 5 6
3 2 7 8

Problem C. Hot-keys

Author:A. Klenin   Time limit:5 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

When designing dialog forms for interactive programs, it is important to assign hot-keys (known also as accelerator keys) to each dialog element, so as to facilitate keyboard input.

For better mnemonics, hot-keys are assigned based on the letters of dialog elements' captions, usually favoring letters near the beginning of caption. Manual hot-keys distribution can be tedious and error-prone, as one must be careful not to assign same letter to different elements.

Your program will be given a list of captions. It must assign unique hot-keys to as many captions of possible. Each assigned hot-key must be a letter from the corresponding caption.

For each hot-key, position is the leftmost occurrence of the hot-key letter in the corresponding caption. From all solutions with the same numbers of hot-keys, your program must choose the one with minimal sum of hot-key positions. If there is still more than one optimal solution, output any of them.

Input file format

Input file contains number of captions N followed by N lines with captions.

Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
yes
no
cancel
&yes
&no
&cancel
2
4
abc
bca
acb
aaaa
&abc
&bca
a&cb
aaaa

Задача D. Длинный текст и много слов (revisited)

Автор:A. Klenin   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Имеется текст и N слов. Длина текста составляет L символов, длина каждого слова — от 1 до 1000 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из маленьких латинских букв.

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

В первой строке входного файла содержится текст, во второй — число N, в следующих N строках — слова.

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

В выходном файле должны содержаться N чисел 1 или 0, обозначающих, что соответствующее слово входит или не входит в текст.

Ограничения

1 ≤ L ≤ 250000, 1 ≤ N ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
longlongstring
2
short
string
0 1

Задача E. Коммивояжёр возвращается!

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!

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

Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!

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

В системе Альфы Центавра n планет. Это число записано в первой строке входного файла. Следующие n строк содержат по n чисел каждая: j-ое число на i-ой из этих строк — стоимость перемещения aij от i-ой планеты до j-ой. Числа в каждой строке разделены пробелами. aij = -1 означает, что из планеты i нельзя на прямую добраться до планеты j.

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

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

Ограничения

1 ≤ n ≤ 19, aij ≤ 108

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
-1 1 6
3 -1 7
4 9 -1
5
2
4
-1 1 1 1
1 -1 1 1
1 1 -1 1
1 1 1 -1
3

0.040s 0.005s 15