시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 192 | 58 | 44 | 27.673% |
한 범죄 조직에서의 오랜 기간에 걸친 첩보 활동 끝에, 당신은 이제 그 조직을 와해시킬 시도를 해보려 한다. 하지만 당신 혼자서는 이 일을 성공적으로 끝낼 수 없다. 그래서 당신은 조직원 몇 명을 매수해 일을 진행하려 하지만, 당신에게 주어진 예산은 한정되어 있다.
다행히도 당신은 사람을 파악하는 데 천부적인 재능이 있다. 그래서 어떤 조직원이 조직을 배반할 생각이 있다면, 당신은 그에게 어느 정도의 돈을 줘야 할 지를 이미 알고 있다. 게다가, 당신은 그들이 성공적으로 변절하여 완벽히 당신의 편이 될 확률까지도 알고 있다. 특별히 다른 방법이 존재하지 않기에 당신은 이제부터 실제로 조직원들에게 직접 접근하여 매수를 시도하려 한다. 만일 어떤 조직원이 돈을 받고도 매수되지 않았다면 당신은 다시는 그 조직원을 매수하려 시도할 수 없다.
각 조직원들에 대한 정보, 즉 그들이 요구할 돈과 변절할 확률이 주어지고, 당신이 필요한 최소한의 변절자 수가 주어질 때, 과연 이번 계획이 어느 정도의 확률로 성공할 지 계산할 수 있을까?
입력의 첫 줄엔 테스트 케이스의 수가 주어진다. 이 수는 100을 넘지 않는다.
각 테스트 케이스는 다음과 같이 구성된다.
각 테스트 케이스에 대해 다음을 출력한다.
2 4 3 1000 300 40 300 50 300 60 300 70 4 2 1000 100 80 700 50 400 20 500 20
0.21 0.408
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 B번