Jane의 꽃집

Jane은 지역 꽃 시장에 꽃집을 열 계획이다. 초기 비용에는 매장 허가, 비품과 장식, 온실에서 가게로 꽃을 운반할 트럭 등이 포함된다. Jane은 수입을 벌어 이러한 비용을 회수해야 한다. 그녀는 향후 M개월 동안 각 달에 얼마의 순수입을 올릴지 추정했다.

Jane은 M개월의 기간에 대한 IRR (Internal Rate of Return)를 계산하여 자신의 꽃집이 얼마나 성공할지 예측하고자 한다. (시간, 현금 흐름) 쌍 (i, $C_{i}$)의 열이 주어질 때, IRR은 마지막 달이 끝날 때 총현금이 정확히 0이 되게 하는 복리 이자율이다. IRR이 높을수록 사업은 더 성공적이다. IRR이 물가 상승률보다 낮다면, 애초에 사업을 시작하지 않는 것이 현명할 것이다.

예를 들어, 초기 비용이 $10,000이고 가게를 3개월 동안 운영하며 순수입이 각각 $3,000, $4,000,$5,000이라고 하자. 그러면 IRR r은 다음과 같이 주어진다.

이 경우 방정식을 만족하는 이율은 단 하나(~=8.8963%)뿐이다.

Jane이 자신의 사업에 대한 IRR을 계산하도록 도와주자. -1 < r < 1임이 보장되며, 각 테스트 케이스에는 정확히 하나의 해가 있다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. $C_{0}$ > 0. 0 ≤ $C_{i}$ ≤ 1,000,000,000.

소규모 데이터 세트(테스트 세트 1 - 공개)

1 ≤ M ≤ 2.

대규모 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ M ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 꽃집을 운영할 개월 수를 나타내는 양의 정수 M으로 시작한다. 다음 줄에는 음이 아닌 정수 M + 1개 $C_{i}$ (0 ≤ i ≤ M)가 주어진다. $C_{0}$은 초기 비용을 나타내고, 나머지 모든 $C_{i}$들은 이익을 나타낸다는 점에 유의하라. 가게는 매달 항상 양의 순이익 또는 순이익 없음 중 하나를 기록하며, 음의 이익을 기록하는 일은 없다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 (1부터 시작하는) 테스트 케이스 번호이고, y은 사업의 IRR of Jane's을 나타내는 부동소수점 수이다. y은 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고하라.

예제 케이스 #1에서 IRR은 0이며, Jane은 이자 없이 지불한 돈을 모두 회수했을 뿐이다. 예제 케이스 #2와 #3은 대규모 데이터 세트에만 등장한다.