cho.sh

속임수 룰렛

예산 B 안에서 37개 룰렛 숫자에 정수 베팅을 나누어 담고 가장 적게 걸린 번호에 떨어지는 공에서 기대 수익을 최대화합니다.

보통7그리디정렬확률수학아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

카지노에서 룰렛을 한다. 룰렛에는 0부터 36까지 37개의 번호가 있고, 참가자는 원하는 번호에 돈을 건다. 모두가 베팅을 마치면 휠을 돌리고, 공은 결국 번호 하나 위에 멈춘다. 그 번호에 돈을 건 사람은 건 금액의 36배를 돌려받는다. 즉 그 베팅의 순이익은 건 금액의 35배다. 다른 번호에 건 돈은 모두 잃는다.

밤새 잃기만 하다가 규칙 하나를 알아냈다. 공은 항상 걸린 돈의 합이 가장 적은 번호에 멈춘다. 그런 번호가 여럿이면 그중 하나에 균등한 확률로 멈춘다.

당신은 다른 참가자가 모두 베팅을 끝낸 뒤에 베팅한다. 남은 예산은 BB이고, 서로 다른 번호 0개 이상에 베팅할 수 있다. 각 베팅 금액은 양의 정수이고 번호마다 달라도 되지만, 합이 BB를 넘을 수는 없다. 순이익의 기댓값을 최대로 만들어라.

순이익은 공이 멈춘 번호에 당신이 건 금액의 36배에서 당신이 건 금액의 합을 뺀 값이다. 아무 번호에도 베팅하지 않으면 순이익이 0이므로 답은 항상 0 이상이다.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에 남은 예산 BB와 다른 참가자가 돈을 건 번호의 개수 NN이 공백으로 구분되어 주어진다. 둘째 줄에 정수 NN개가 주어지며, ii번째 정수 XiX_i는 그 번호에 다른 참가자가 건 금액의 합이다. 이 NN개의 번호는 서로 다르고, 나머지 37−N37 - N개의 번호에는 아무도 돈을 걸지 않았다.

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤371 \le N \le 37
  • 1≤B≤10121 \le B \le 10^{12}
  • 1≤Xi≤10121 \le X_i \le 10^{12}

출력

각 테스트 케이스마다 한 줄에 Case #x: 를 출력하고 이어서 순이익 기댓값의 최댓값을 소수점 아래 10자리까지 반올림해 출력한다. xx는 1부터 시작하는 테스트 케이스 번호다. 소수점 아래 자리가 부족하면 0으로 채운다.

정확한 답은 분모가 37 이하인 유리수이므로 반올림한 결과는 하나로 정해진다. 다만 값이 3×10133 \times 10^{13}에 이를 수 있어 배정밀도 부동소수점으로는 소수점 아래 10자리를 정확히 찍을 수 없다. 분자와 분모를 정수로 들고 마지막에 자리를 맞춰 출력하라.

힌트

비어 있는 번호가 34개이고 나머지 세 번호에 5, 6, 7이 걸려 있으며 예산이 34라면, 비어 있는 34개 번호에 1씩 건다. 이 34개 번호의 합이 모두 1이 되어 공은 반드시 그중 하나에 멈추고, 36을 돌려받아 순이익은 36−34=236 - 34 = 2다.

비어 있는 번호가 33개이고 두 번호에 1, 다른 두 번호에 10이 걸려 있으며 예산이 34라면, 비어 있는 33개 번호에 1씩 건다. 그러면 합이 1인 번호가 35개가 되고, 그중 33개에만 당신의 돈이 걸려 있다. 확률 33/3533/35로 36을 돌려받으므로 기댓값은 3335×36−33\frac{33}{35} \times 36 - 33이다.