문제
2*N 명의 선수들이 두 팀으로 나뉘어 축구를 한다. 각 선수는 소속팀이 있고, 팀 내에서 고유 번호( 1 ~ N)를 갖고 있으며 슈팅시 골을 넣을 수 있는 확률을 나타내는 정확도를 갖고 있다. 또한 한 선수가 공을 가지고 있을 때 패스를 해줄 수 있는 자기 팀 선수의 번호와 상대팀 선수 중에 공을 빼앗을 수 있는 선수들의 번호를 알고 있다. 선수는 공을 소유하고 있는 상태에서 정확히 1초 후에 아래 3가지 중의 하나의 사건을 일으킨다.
- 자기 팀 내에 패스 해줄 수 있는 선수에게 random 하게 패스한다.(F)
- 상대팀 선수 중에 공을 빼앗을 수 있는 선수한테 random하게 빼앗긴다.(E)
- 슛을 시도한다.
선수가 슛을 시도한 경우 골을 넣을 확률은 각 선수의 정확도와 같다. 한 선수가 슛을 시도한 경우 골인의 성공여부와 상관없이 골은 상대편 1번 선수에게 넘어간다.
위 3개의 사건이 일어나는 비율은 |F| : |E| : 1 이며 기준이 되는 선수는 현재 공을 소유한 선수가 된다.
"random" 의 의미는 예를 들어 패스가 가능한 선수가 4명이라고 할 경우 4명 모두에게 25%의 비율로 패스 할 수 있다는 의미이고 빼앗을 수 있는 선수가 4명이라고 할 경우 4명 모두에게 빼앗길 확률이 25%로 같다는 의미이다.
게임은 첫 번째 팀 1번 선수로부터 시작되며 어느 팀이든 R 골을 넣거나 T 초가 지나면 게임은 종료된다. 가능한 모든 최종 결과(score)에 대한 확률을 구하는 프로그램을 작성하시오.
아래 그림은 두 번째 <입력 예> 에 대한 그림이다.
입력
첫 행에 각 팀의 선수들의 수를 나타내는 양의 정수 N( 1 ≤ N ≤ 100), 승부를 결정하는 골인의 수를 나타내는 R(1 ≤ R ≤10), 게임 시간을 나타내는 T( 1≤ T ≤ 500) 가 공백으로 구분되어 주어진다.
다음 N 개의 행에 첫 팀의 각 선수들에 대한 정보가 행으로 구분하여 주어진다. 각 행의 첫 수는 실수 타입으로 선수의 정확도를 의미한다. 다음으로는 정수로서 패스가 가능한 선수의 수 nF( 0 ≤ nF ≤ N-1), 공을 빼앗을 수 있는 상대편 선수의 수 nE( 0 ≤ nE ≤N)가 주어지고 이어서 nF 명의 우리 편 선수의 번호와 nE 명의 상대편 번호가 공백으로 구분하여 주어진다. nF의 범위가 0 ≤ nF ≤ N-1 인 것은 자기 자신은 제외하기 때문이다.
이어서 N 개의 행에 두 번째 팀의 각 선수들에 대한 정보가 행으로 구분하여 주어진다. 형식은 첫 팀과 같다.
출력
경기 결과는 이론적으로 R*(R + 2)가지의 경우가 있다. 각 결과에 대한 확률을 소수 6자리까지 행으로 구분하여 출력하시오. 허용되는 오차 범위는 0.000001이다. 출력 순서는 스코어의 오름차순을 기준으로 출력하시오. (첫 팀의 점수가 작은 것을 우선으로, 두 번째 팀의 점수가 작은 것을 차선으로 한다.)
예제1
입력
112
0.5011
0.5011
출력
0.562500
0.187500
0.250000
예제2
입력
225
0.012212
1.000
0.5102
0.5101
출력
0.257813
0.281250
0.070313
0.171875
0.164063
0.023438
0.015625
0.015625
힌트
출처
COCI 2012/2013 contest5 6