Problem A. 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

Problem B. 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 C. Multiplication puzzle ≡

Statement

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.

The goal is to take cards in such order as to minimize the total number of scored points.

For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring 10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000

If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be 1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

Input file format

Output file format

Constraints

Sample tests

6
10 1 50 50 20 5

3650

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

Условие

Скрытая модель Маркова предназначена для описания стохастически эволюционирующих во времени процессов. Она представляет из себя ориентированный граф состояний, ребрам которого приписаны веса 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