Задача A. Домой на электричках

Автор:X командный чемпионат Санкт-Петербурга по программированию - V Открытая Кировская командная олимпиада   Ограничение времени:2 сек
Входной файл:a.in   Ограничение памяти:8 Мб
Выходной файл:a.out  

Условие

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

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

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

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

Во входном файле записаны сначала числа N и E. Затем записано число M, обозначающее число рейсов электричек. Далее идет описание M рейсов электрички. Описание каждого рейса электрички начинается с числа Ki — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

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

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

Ограничения

2 ≤ E ≤ N ≤ 1000, 1 ≤ M ≤ 100, 2 ≤ Ki ≤ N.

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

Входной файл (a.in) Выходной файл (a.out)
1
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
20

Problem B. Bureaucracy generator

Author:I. Ludov, A.Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

A large software company has started a new high-budget project — the game console platform called "Y-Sphere". The company is proud of its sophisticated development process standards, and has recently received a prestigious CMM (Capacity for Managers Maximization) certificate.

Using those powerful standards, it was easily calculated that the project will need precisely S developers. Now the only problem is how to manage them efficiently. Fortunately, CMM process has the answer: of course a proper management hierarchy is needed, that can be built by following few simple rules:

  1. Each manager has managerial capacity — number of immediate subordinates he can control. He must be assigned to manage neither more (too difficult for him), nor less (not efficient enough).
  2. Each manager's immediate subordinates must be either all managers (who in turn have their own subordinates), or all developers.
  3. Each developer and manager has exactly one immediate superior manager, except a single highest level manager called Project Leader, who has none.
  4. Each manager must have capacity strictly lower then his immediate superior (so that more qualified managers take higher positions in hierarchy).

The company has managers of N different capacities. It has unlimited number of managers of each capacity.

Your program must plan a proper management hierarchy or determine that it is impossible.

Input file format

Input contains two integers S N, followed by N different integers ai — available managerial capacities.

Output file format

Output must contain integer M — total count of required managers, who are numbered from 1 to M. Next must be M pairs of integers si ci, where si is the number of i-th manager's immediate superior (or zero for Project Leader), ci is capacity of i-th manager, taken from the list of available capacities. If the there is no solution, output a single number 1. If there is more than one solution, output any of them.

Constraints

1 ≤ S, ai, ci ≤ 100, 1 ≤ N ≤ 10

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 3
3 1 2
4
0 3
1 2
1 1
1 1
2
5 2
1 2
-1

Задача C. Вторая задача для СММ

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

Условие

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

Кроме того, для каждого состояния известна вероятность bi того, что оно окажется начальным.

Для стороннего наблюдателя состояние не является доступной напрямую информацией — оно скрыто. Зато он может видеть некоторый производимый системой сигнал, распределение вероятностей которого зависит от состояния. Таким образом, задание модели завершается указанием матрицы cij — вероятности наблюдать сигнал j при том, что система находится в состоянии i.

Вторая задача для СММ состоит в том, чтобы по данной модели aij bi cij установить последовательность состояний w1, ..., wk, которая бы являлось наиболее вероятной для данной последовательности сигналов s1, ... , sk. Напишите программу, которая решает эту задачу.

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

Первая строка входного файла содержит числа N, M, K — количество состояний, уровней сигнала и длину последовательности наблюдений соответственно.

Вторая строка содержит N чисел bi.

Следующие N строк содержат по N действительных чисел от 0 до 1 и задают матрицу aij, где i — номер строки, а j — столбца. Сумма элементов каждой строки равна единице.

Следующие N строк содержат по M чисел от 0 до 1 и задают матрицу cij.

Последняя строка содержит K целых чисел от 1 до M и задает последовательность наблюдений si

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

В выходной файл выведите K целых чисел wi.

Ограничения

1 ≤ N, M, K ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 8
0 0 1
0.4 0.3 0.3
0.2 0.6 0.2
0.1 0.1 0.8
1 0 0
0 1 0
0 0 1
3 3 3 1 1 3 2 3
3 3 3 1 1 3 2 3

0.124s 0.006s 17