Задача A. Min-cost-max-flow aka В поисках невест
Условие
Однажды король Флатландии
решил отправить 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
|
Задача B. Слово из кубиков
Условие
Имеется
N кубиков, на гранях которых написаны буквы.
Требуется определить, можно ли из этих кубиков составить данное слово длиной
K символов,
и если да, то вывести номера использованных кубиков.
При этом каждый кубик можно использовать только один раз.
Если решений несколько, выдать любое из них.
Формат входного файла
В первой строке входного файла содержится количество кубиков
N.
Во второй строке — слово, в следующих
N строках — по шесть символов без разделителей,
определяющих буквы на гранях кубиков. (Порядок букв не имеет значения).
Формат выходного файла
Выходной файл должен содержать последовательность из
K различных целых чисел от
1 до
N,
задающих номера кубиков для каждой буквы слова, начиная с первой.
Если решения нет, выходной файл должен содержать единственное число 0.
Ограничения
1 ≤ N, K ≤ 12.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
|
2 5 3 4
|
Задача C. Длинный текст и много слов (revisited)
Условие
Имеется текст и
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
|
