코어 훈련

Writing Code Jam 문제는 어렵기 때문에, 새로운 아이디어를 생각해 내기 위한 AI를 만들었다. AI의 창의성을 최대한 높이기 위해, 각각 고유한 "personality"을 지닌 서로 다른 N개의 "cores"을 주었다. 하지만 사람과 마찬가지로 이 코어들도 주의가 흐트러지거나 손상되거나 작동을 거부할 수 있다. i번째 코어가 올바르게 작동할 성공 확률은 $P_{i}$이다. 적어도 K개의 코어가 올바르게 작동하기만 하면 AI도 올바르게 작동한다. 그렇지 않으면 아마 사악해져서 직접 설계한 극악한 퍼즐의 미로에 우리를 가둘 것이다. 그리고 Code Jam에 무슨 짓을 할지 누가 알겠는가? 어려운 확률 문제를 잔뜩 작성할지도 모른다!

이런 일을 방지하기 위해, 코어 가운데 하나 이상을 훈련하여 신뢰성을 높일 계획이다. 코어를 개선하는 데 사용할 수 있는 "훈련 단위"가 총 U만큼 있다. i번째 코어에 X단위를 사용하면 성공 확률에 X가 더해진다. 훈련 단위는 원하는 방식으로 코어들에 나누어 줄 수 있으며, 하나 이상의 코어가 아무 단위도 받지 않을 수도 있다. 물론 코어의 성공 확률을 1보다 높게 올릴 수는 없다.

AI가 올바르게 작동할 확률을 최대화하도록 훈련 단위를 배정한다면, 그 확률은 얼마인가?

이 문제 풀기

이 문제에는 작은 데이터 세트가 2개 있고 큰 데이터 세트는 없다. 두 번째 작은 데이터 세트에 도전하려면 먼저 첫 번째 작은 데이터 세트를 해결해야 한다. 두 데이터 세트 중 어느 것이든 다시 시도할 수 있다(시간 페널티가 부과된다).

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ N ≤ 50. 모든 i에 대해, 0.0000 ≤ $P_{i}$ ≤ 1.0000. 0.0000 ≤ U ≤ N - 모든 $P_{i}$의 합. (사용할 수 있는 양보다 많은 훈련 단위가 주어지지 않는다.)

작은 데이터 세트 1 (테스트 세트 1 - 공개)

시간 제한: 20초. K = N. (AI가 올바르게 작동하려면 모든 코어가 올바르게 작동해야 한다.)

작은 데이터 세트 2 (테스트 세트 2 - 공개)

시간 제한: 40초. 1 ≤ K ≤ N.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에는 코어의 총개수 N과 AI가 올바르게 작동하기 위해 성공해야 하는 코어의 최소 개수 K까지 두 정수가 주어진다. 둘째 줄에는 훈련 단위의 수를 나타내는 하나의 유리수 U가 주어진다. 셋째 줄에는 N개의 유리수 $P_{i}$가 주어지며, 이 중 i번째 수는 i번째 코어가 올바르게 작동할 확률을 나타낸다. 이 확률들은 모두 소수점 이하 정확히 네 자리의 정밀도로 주어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 훈련 단위를 최적으로 배정했을 때 AI가 올바르게 작동할 확률이다. y가 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ를 참고한다.

마지막 두 예제 케이스는 작은 데이터 세트 1에는 나오지 않는다는 점에 유의한다.

예제 케이스 #1에서는 모든 코어의 성공 확률을 1로 만들 만큼 충분한 훈련 단위가 있으므로, AI는 반드시 올바르게 작동한다.

예제 케이스 #2에서는 AI가 올바르게 작동하려면 두 코어가 모두 올바르게 작동해야 하므로, 각 코어에 적어도 약간의 훈련 단위를 주어야 한다. 최선의 선택은 각 코어를 0.5까지 훈련하는 것으로 밝혀진다. 그러면 AI가 올바르게 작동할 확률은 0.5 × 0.5 = 0.25이다. 다른 모든 배정은 이보다 열등하다. 예를 들어 한 코어는 0.9까지, 다른 코어는 0.1까지 훈련하면 성공 확률은 0.9 × 0.1 = 0.09에 불과하다.

예제 케이스 #3에서는 사용할 훈련 단위가 없으며, AI가 올바르게 작동하려면 두 코어 중 적어도 하나가 올바르게 작동해야 한다. 먼저 AI가 올바르게 작동하지 않을 확률을 계산하는 방식으로 접근할 수 있는데, 이는 두 코어가 모두 올바르게 작동하지 못할 때에만 발생한다. 두 코어가 모두 실패할 확률은 (1 - 0.9) × (1 - 0.8) = 0.02이다. 따라서 적어도 하나의 코어가 올바르게 작동하고, 그에 따라 AI가 올바르게 작동할 확률은 1 - 0.02 = 0.98이다.

예제 케이스 #4에서 최적 전략은 모든 훈련 단위를 두 번째 코어에 주는 것이다. 그러면 적어도 하나의 코어가 올바르게 작동할 확률은 1 - (0.4 × 0.6) = 0.76가 된다. 다른 모든 선택은 이보다 열등하다. 예를 들어 모든 훈련 단위를 첫 번째 코어에 주면 0.75밖에 얻지 못하고, 코어들에 똑같이 나누어 주면 0.7525가 된다.