Задача 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.027s 0.005s 15