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

Условие

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

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

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

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

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

Ограничения

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

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 ≡

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

Output file format

Constraints

Sample tests

4 3
3 1 2

4
0 3
1 2
1 1
1 1

5 2
1 2

-1

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

Условие

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

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

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

Вторая задача для СММ состоит в том, чтобы по данной модели a_ij b_i c_ij установить последовательность состояний w₁, ..., w_k, которая бы являлось наиболее вероятной для данной последовательности сигналов s₁, ... , s_k. Напишите программу, которая решает эту задачу.

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M, K ≤ 100

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

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