암호 문제

나는 매우 긴 암호를 가지고 있으며, 가끔 암호를 입력할 때 실수한다. 지금은 암호의 일부를 입력했지만, 몇 번의 실수를 했을 수도 있다. 특히 앞의 문자 중 하나 이상을 입력하면서 잘못된 키를 눌렀을 수도 있다. 각 문자를 올바르게 입력했을 가능성이 주어질 때, 어떻게 해야 할까?

나에게는 세 가지 선택지가 있다:

• 암호 입력을 마친 다음 "enter"를 누른다. 나머지 문자는 완벽하게 입력할 수 있다는 것을 알고 있다. 앞서 입력한 문자 중 하나라도 잘못된 것으로 드러나면, 전체를 다시 입력하고 "enter"를 다시 눌러야 하지만 두 번째에는 올바르게 입력할 수 있다는 것을 알고 있다.

• "backspace"를 몇 번 눌러 마지막에 입력한 문자를 삭제한 다음, 선택지 1에서처럼 암호 입력을 완료하고 "enter"를 누른다. 삭제하지 않은 문자 중 하나라도 잘못되었다면, 전체를 다시 입력하고 "enter"를 눌러야 하며, 두 번째에는 올바르게 입력할 수 있다는 것을 알고 있다.

• "enter"를 눌러 포기하고, 암호를 처음부터 다시 입력한 뒤 "enter"를 다시 누른다. 이번에는 올바르게 입력할 수 있다는 것을 알고 있다.

필요한 키 입력 횟수의 기댓값을 최소화하고 싶다. 암호의 각 문자를 입력하는 데는 1번의 키 입력이 필요하고, 각 "backspace"에는 1번의 키 입력이 필요하며, 시도를 완료하거나 포기하기 위해 "enter"를 누르는 데는 1번의 키 입력이 필요하다.

참고: 키 입력 횟수의 "expected" 값은 같은 상황이 매우 많이 발생했을 때 필요한 키 입력 횟수의 평균이다. 아래 예제를 참고하라.

예제

암호가 "guest"이고 이미 처음 두 문자를 입력했지만, 각 문자를 입력할 때 실수할 확률이 40%였다고 하자. 그러면 네 가지 경우가 있다:

• 오류 없이 "gu"를 입력했다. 이 경우는 0.6 * 0.6 = 0.36의 확률로 발생한다.

• 'g'는 올바르게 입력했지만 'u'를 입력할 때 실수했다. 그러면 여전히 두 글자를 입력한 상태이지만 두 번째 글자는 잘못되어 있다: "gX". (여기서 'X' 문자는 잘못 입력한 글자를 나타낸다.) 이 경우는 0.6 * 0.4 = 0.24의 확률로 발생한다.

• 'u'는 올바르게 입력했지만 'g'를 입력할 때 실수했다: "Xu". 이 경우는 0.4 * 0.6 = 0.24의 확률로 발생한다.

• 두 글자를 모두 입력할 때 실수했으므로, 잘못된 글자가 두 개 있다: "XX". 이 경우는 0.4 * 0.4 = 0.16의 확률로 발생한다.

실제로 몇 번의 실수를 했는지는 알 수 없지만, 어떤 전략에 대해서든 그 전략을 사용하는 데 필요한 키 입력 횟수의 기댓값을 계산할 수 있다. 이는 아래 표에 나와 있다:

계속 입력한다면 0.36의 확률로 4번의 키 입력이 필요하고, 0.64의 확률로 10번의 키 입력이 필요하다. 이 시행을 여러 번 반복한다면 전체의 36%에서는 4번의 키를 입력하고, 나머지 64%에서는 10번의 키를 입력하므로, 필요한 키 입력 횟수의 평균은 0.36 * 4 + 0.64 * 10 = 7.84가 된다. 하지만 이 경우에는 즉시 엔터를 누르는 편이 더 좋으며, 여기에는 7번의 키 입력이 필요하다.

제한

시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB. 1 ≤ T ≤ 20. 모든 i에 대해 0 ≤ $p_{i}$ ≤ 1.

테스트 세트 1 (Visible Verdict)

1 ≤ A ≤ 3. A < B ≤ 100.

테스트 세트 2 (Hidden Verdict)

1 ≤ A ≤ 99999. A < B ≤ 100000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 A와 B가 들어 있는 줄로 시작한다. A는 이미 입력한 문자의 수이고, B는 암호의 전체 문자 수이다.

그다음 줄에는 A개의 실수 $p_{1}$, $p_{2}$, ..., $p_{A}$가 주어진다. $p_{i}$는 암호의 $i^{th}$번째 글자를 올바르게 입력했을 확률을 나타낸다. 이 실수들은 십진 숫자와 최대 하나의 소수점으로 구성된다. 소수점이 수의 첫 번째 문자나 마지막 문자인 경우는 없다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 지금까지 입력한 글자를 제외하고 앞으로 필요한 추가 키 입력 횟수의 기댓값으로, 최적의 전략을 선택한다고 가정한다. y의 절대 오차 또는 상대 오차는 10^{-6} 이내여야 한다.