Задача A. Дорога в аэропорт ≡

Условие

Город соединяется с аэропортом автодорогой, имеющей N полос движения. Дорога состоит из K участков длиной 10 километров каждый. На каждом участке полосы разделены сплошной линией разметки (т.е. сворачивать с одной полосы на другую запрещено). На стыке участков разрешено перемещение на любую из соседних полос. В начале каждого участка на каждой полосе дороги поставлен знак ограничения скорости, при этом на разных полосах ограничения могут различаться.

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

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

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

Ограничения

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

1 3
70 60 40

0.559

3 2
1 10000
1 1
100 1

10.001

Problem B. Nearest number - 2 ≡

Statement

Input is the matrix A of N by N non-negative integers.

A distance between two elements A_i j and A_p q is defined as |i − p| + |j − q|.

Your program must replace each zero element in the matrix with the nearest non-zero one. If there are two or more nearest non-zeroes, the zero must be left in place.

Input file format

Output file format

Constraints

Sample tests

3
0 0 0
1 0 2
0 3 0

1 0 2
1 0 2
0 3 0

Задача C. Первая задача для СММ ≡

Условие

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

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

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

Первая задача для СММ состоит в том, чтобы по данной модели a_ij b_i c_ij установить вероятность появления заданной последовательности сигналов 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.

Ограничения

1 ≤ M ≤ 100

1 ≤ N ≤ 5

1 ≤ K ≤ 10

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

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

1.53600000000000E-0004