일본식 술집
시간 제한8초메모리 제한512 MB
음료별 주문 수와 혼동 확률 행렬이 주어질 때, 배달된 음료 구성이 주문한 구성과 일치할 확률의 자연로그를 구한다.
문제
친한 친구들과 술자리(일본어로 노미카이)를 하러 일본식 술집, 일본어로 이자카야에 들어왔다.
이제 참가자들이 요청한 대로 독한 술과 순한 음료의 잔을 주문하려 한다. 그런데 일반적인 이자카야의 직원은 대부분 아르바이트생이라 일에 익숙하지 않아 주문마다 일정 확률로 실수를 한다.
너는 이런 실수를 걱정하고 있다. 오늘은 소중한 친구들인 참가자들에게 즐거운 날이다.
주어진 모든 주문에 대해 이자카야 직원이 올바른 음료를 가져올 확률을 계산하는 프로그램을 작성하라. 직원의 실수로 결과적으로 올바른 음료가 전달된 경우도 너에게는 받아들일 수 있으므로 확률에 포함한다.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 N (1 ≤ N ≤ 8)이 있는 줄로 시작한다. 정수 N은 이자카야에서 제공하는 음료의 종류 수다.
다음 N개 줄은 아래 형식으로 음료에 대한 확률을 나타낸다.
p11 p12 . . . p1N
p21 p22 . . . p2N
...
pN1 pN2 . . . pNN
각 실수 pij는 음료 i를 주문했을 때 직원이 음료 j의 잔을 가져올 확률이다. 1 ≤ i, j ≤ N에 대해 pij ≥ 0이고 p**i1 + p**i2 + . . . + p**iN = 1이다. 각 테스트 케이스 끝에는 N이 있는 줄이 온다. i번째 정수 ni는 참가자들이 음료 i를 주문한 횟수다 (0 ≤ ni ≤ 4).
마지막 테스트 케이스 다음에는 0이 있는 줄이 온다.
출력
각 테스트 케이스마다 테스트 케이스 번호(1부터 시작)와, 직원이 주어진 모든 주문에 대해 올바른 음료를 가져올 확률의 자연로그를 한 줄에 출력한다. 결과는 소수점 아래 여덟 자리까지 출력한다. 어떤 경우에도 직원이 올바른 음료를 가져올 수 없다면 대신 “-INFINITY”를 출력한다. 출력 형식은 예시 출력을 따른다.