
ZOJ Problem Set  2528
As the master of weather forecast program appeared on television every day, Vivian is very interested in studying knowledge of weather forecast. She found that the forecast is in fact an approximate estimation of the weather in future. Further more, the observation of weather by human's eyes sometimes befools ourselves. For example, actually it is cloudy today, but the observer mistakes it into windy. It seems like a childish fault but it has really happened for more than once and makes this forecast job much more difficult. This discovery strongly enhances Vivian's interest so she takes a try to research on weather forecast now. Let's describe the problem mathematically. There are N kinds of weathers {1, 2, ... , N} in all, such as "sunny", "rainy", "foggy", and so on. For a kind of weather i (1 <= i <= N), suppose the probability of mistaking it into weather j (1 <= j <= N) is A[i][j]. And for a certain day with weather i, the probability of the next day with weather j is B[i][j]. Given the probability of weather in the first day and the observation reports in M days, what are the weathers in these M days? Input The input consist of several test cases. In the first line of each case there is an integer N (0 < N <= 100), indicating the total number of different kinds of weathers. Then two matrices A and B follow (A before B), indicating the probabilities of mistaken observation and weather variation, which is referred above. Of course, all the floating numbers in the matrices are in the range (0, 1) and the sum of numbers in every row equals 1. The next line contains N floating numbers denoting the initial probability distribution of the weather in the first day (all are positive and the sum of them equal to 1), where the i^{th} number means the probability of weather i in the first day. The last line contains M (0 < M <= 100) integers indicating the observations in these M days (including the first day), with each integer in the range [1, N]. The input ends with a case where N = 0. There is a blank line between adjacent cases. Output For each case, output M integers on a single line with each number in the range[1, N], representing the most possible weathers in these M days. Print a blank line after each case except the last one. Sample Input 2 0.6 0.4 0.4 0.6 0.3 0.7 0.6 0.4 0.5 0.5 1 1 2 1 0 Sample Output 2 1 2 1 Author: JIANG, Hao Source: ZOJ Monthly, September 2005 