cho.sh

레지스탕스

지난 임무의 참가자와 사보타주 횟수가 주어질 때, 스파이가 없을 확률이 가장 높은 Q명의 팀을 골라 그 확률을 출력한다.

보통7확률조합론완전 탐색아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

레지스탕스는 소수의 저항군이 부패한 정부와 맞서는 보드게임이다. 저항군은 정부를 무너뜨리려고 임무를 이어서 수행하지만, 조직에는 이미 첩자가 숨어 있다. 임무에 나간 팀에 첩자가 한 명만 있어도 임무는 무너질 수 있으므로 팀은 신중하게 골라야 한다.

이 문제는 그 게임을 단순하게 바꾼 것이다. 플레이어는 N명이고 그중 S명이 무작위로 첩자가 된다. 첩자를 고르는 방법은 (NS)\binom{N}{S}가지이고 모두 나올 확률이 같다. 각 플레이어는 자신이 첩자인지는 알지만 다른 사람이 첩자인지는 모른다.

한 게임은 임무 5개로 이루어진다. 임무마다 정해진 수의 플레이어가 팀이 되고, 팀에 들어간 첩자는 각자 공정한 동전을 던져 임무를 방해할지 정한다. 즉 팀에 들어간 첩자 한 명이 방해할 확률은 정확히 1/21/2이고, 첩자들의 결정은 서로 독립이다. 임무가 끝나면 방해 횟수만 공개되고 누가 방해했는지는 공개되지 않는다.

이미 끝난 임무 M개의 기록이 주어진다. i번째 임무에는 플레이어 CiC_i명이 참여했고 방해가 FiF_i번 있었으며, 참여한 플레이어의 번호도 주어진다.

이제 다음 임무에 나갈 팀으로 서로 다른 플레이어 Q명을 고른다. 주어진 기록을 조건으로 할 때 팀에 첩자가 없을 조건부확률이 가장 큰 팀을 고르고, 그 확률을 출력한다.

입력

입력은 게임 여러 개로 이루어진다. 게임은 100개 이하이다.

각 게임의 첫 줄에는 N, S, M, Q가 공백으로 구분되어 주어진다. 차례로 플레이어 수, 첩자 수, 이미 끝난 임무 수, 다음 임무에 고를 플레이어 수이다. (2≤N≤152 \le N \le 15, 1≤S≤N−11 \le S \le N - 1, 1≤M≤41 \le M \le 4, 1≤Q≤N−S1 \le Q \le N - S)

둘째 줄에는 C1,…,CMC_1, \dots, C_M이 공백으로 구분되어 주어진다. (1≤Ci≤N1 \le C_i \le N)

셋째 줄에는 F1,…,FMF_1, \dots, F_M이 공백으로 구분되어 주어진다. (0≤Fi≤min⁡(Ci,S)0 \le F_i \le \min(C_i, S))

이어지는 M개의 줄 가운데 i번째 줄에는 i번째 임무에 참여한 플레이어의 번호 CiC_i개가 공백으로 구분되어 주어진다. 번호는 1 이상 N 이하이고 한 줄 안에서 겹치지 않는다.

입력의 마지막 줄은 0 0 0 0이며 이 줄은 처리하지 않는다.

각 게임의 기록은 적어도 한 가지 첩자 배정으로 설명된다. 즉 주어진 방해 횟수가 나올 확률은 0보다 크다.

출력

게임마다 첩자가 없을 확률이 최대가 되도록 Q명을 골랐을 때의 그 확률을 한 줄에 출력한다. 소수점 아래 다섯째 자리까지 정확히 출력한다. 입력은 10−610^{-6} 이하의 오차가 반올림 결과를 바꾸지 않도록 만들어져 있다. 고른 팀의 구성원은 출력하지 않는다.

힌트

예제 입력의 첫 번째 게임에는 플레이어가 4명, 첩자가 2명이다. 끝난 임무는 하나이고 다음 임무에 2명을 골라야 한다. 그 임무에는 플레이어 1과 2가 참여했고 방해가 2번 있었으므로 두 사람이 첩자다. 플레이어 3과 4를 고르면 첩자가 없는 것이 확실하므로 확률은 1이다.

두 번째 게임은 같은 임무에서 방해가 한 번도 없었던 경우다. 첩자 쌍은 6가지다. 1과 2가 첩자이면서 둘 다 방해하지 않을 확률은 16⋅12⋅12=124\frac{1}{6} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{24}이다. 1과 3이 첩자이면서 1이 방해하지 않을 확률은 16⋅12=112\frac{1}{6} \cdot \frac{1}{2} = \frac{1}{12}이고, 임무에 나간 한 명과 나가지 않은 한 명이 첩자인 나머지 세 경우도 값이 같다. 3과 4가 첩자이면 임무에 첩자가 없어서 방해가 없을 확률이 1이므로 이 경우의 확률은 16\frac{1}{6}이다. 방해가 없었다는 조건에서 3과 4가 첩자일 조건부확률은

1/61/24+4⋅1/12+1/6=413\frac{1/6}{1/24 + 4 \cdot 1/12 + 1/6} = \frac{4}{13}

이다. 그래서 다음 임무에 1과 2를 고르면 첩자가 없을 확률이 4/13≈0.307694/13 \approx 0.30769이고, 이 값이 최댓값이다.

세 번째 게임에서는 임무가 두 개이고 각각 방해가 한 번씩 있었다. 첫 임무에서 한 명, 두 번째 임무에서 한 명을 고르는 것이 최선이다. 예를 들어 1과 3을 고르면 된다. 두 사람이 첩자일 확률이 각각 1/21/2이므로 둘 다 첩자가 아닐 확률은 1/41/4이다.