체육관 게임

체육 시간에 초등학생들이 하는 게임을 확률 과정으로 모형화한다.

게임 설정은 다음과 같다.

• 체육관 바닥의 여러 위치에 $N$개의 바구니가 놓여 있고, 각 바구니에는 서로 구분되는 그림이 붙어 있다.
• 각 바구니 안에는 여러 장의 카드가 들어 있으며, 각 카드에는 이동할 목적지 바구니가 적혀 있다.

진행 방식: 아이들은 지정된 시작 바구니에 모인다. 각자 차례대로 바구니에서 카드 한 장을 무작위로 뽑아 목적지를 외운 뒤, 다음 아이가 뽑기 전에 카드를 도로 넣는다. 선생님이 호루라기를 불면 모든 아이는 자신이 뽑은 카드에 적힌 바구니로 이동한다.

각 바구니의 카드 구성이 주어질 때, 게임의 처음 10단계 동안 한 아이가 각 바구니에 있을 확률을 구하여라.

예를 들어 바구니가 "tree", "house", "car", "park" 네 개이고, 카드 구성이 다음과 같다고 하자.

• "tree" 바구니: "tree" 2장, "house" 1장, "car" 2장
• "house" 바구니: "tree" 1장, "car" 1장, "park" 2장
• "car" 바구니: "tree" 1장
• "park" 바구니: 각 종류 1장씩

이를 표로 정리하면 다음과 같다.

모두 첫 번째 바구니(tree)에서 시작하므로, 처음에는 $P_0(\text{tree}) = 1$이고 나머지 바구니의 $P_0 = 0$이다.

게임 도중 어떤 단계에서 새 위치에 있을 확률은, 직전 단계에 각 위치에 있을 확률과 그 위치에서 새 위치로 이동할 확률의 곱을 모든 위치에 대해 더한 값과 같다. 위 예에서는

$P_{s+1}(\text{tree}) = 0.40\,P_s(\text{tree}) + 0.25\,P_s(\text{house}) + 1.00\,P_s(\text{car}) + 0.25\,P_s(\text{park})$

이다. (예를 들어 tree에서 tree로 갈 확률은 $2/5 = 0.40$, house에서 tree로 갈 확률은 $1/4 = 0.25$이다.)

게임은 항상 첫 번째 바구니에서 시작한다.

입력은 카드 개수 표이며 $N$개의 줄로 이루어진다. $i$번째 줄에는 $i$번 바구니에 들어 있는 카드 개수가 목적지 순서대로 $N$개의 정수로 주어진다. 즉 $j$번째 값은 $i$번 바구니 안에 있는 "$j$번 바구니로 가는" 카드의 장수이다.

바구니 개수 $N$은 입력의 줄 수(그리고 한 줄에 있는 정수의 개수)와 같으며 $2 \le N \le 10$이다. 한 바구니 안에서 같은 목적지 카드는 최대 10장까지 있을 수 있고, 각 바구니에는 카드가 적어도 한 장 들어 있다(각 줄의 합은 1 이상이다).

정확히 10개의 줄을 출력한다. $s$번째 줄($s = 0, 1, \dots, 9$)에는 시작 후 $s$단계가 지났을 때 아이가 각 바구니에 있을 확률 $P_s(1), P_s(2), \dots, P_s(N)$을 공백으로 구분하여 출력한다. 첫 줄은 시작 분포이므로 첫 번째 바구니가 $1.00000$, 나머지가 $0.00000$이다.

각 확률은 소수점 아래 다섯 자리로 반올림하여 출력한다(예: 1.00000). 내부 계산은 배정밀도(double) 실수 연산으로 수행하기를 권장한다.