Cookie Clicker Alpha

이 문제에서는 0개의 쿠키를 가진 상태로 시작한다. 거대한 쿠키를 클릭하여 초당 2개의 비율로 쿠키를 얻는다. C개 이상의 쿠키를 가지고 있을 때는 언제든 쿠키 농장을 살 수 있다. 쿠키 농장을 살 때마다 C개의 쿠키가 들며, 초당 쿠키 생산량이 F개만큼 늘어난다.

농장에 쓰지 않은 쿠키를 X개 가지게 되면 승리한다! 가능한 최선의 전략을 사용할 때 승리하는 데 얼마나 걸리는지 구하라.

예제

C=500.0, F=4.0, X=2000.0라고 하자. 가능한 최선의 전략은 다음과 같이 진행된다.

• 0개의 쿠키를 가지고 시작하며, 초당 2개의 쿠키를 생산한다.

• 250초 후에는 C=500개의 쿠키를 가지게 되며, 초당 F=4개의 쿠키를 생산하는 농장을 살 수 있다.

• 농장을 산 뒤에는 0개의 쿠키가 남고, 전체 쿠키 생산량은 초당 6개가 된다.

• 다음 농장의 가격은 쿠키 500개이며, 약 83.3333333초 후에 살 수 있다.

• 두 번째 농장을 산 뒤에는 0개의 쿠키가 남고, 전체 쿠키 생산량은 초당 10개가 된다.

• 또 다른 농장의 가격은 쿠키 500개이며, 50초 후에 살 수 있다.

• 세 번째 농장을 산 뒤에는 0개의 쿠키가 남고, 전체 쿠키 생산량은 초당 14개가 된다.

• 또 다른 농장을 사려면 쿠키 500개가 들지만, 실제로는 사지 않는 편이 낫다. 대신 쿠키가 X=2000개가 될 때까지 기다리기만 하면 되며, 약 142.8571429초가 걸린다.

총 시간: 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762초.

쿠키는 연속적으로 얻는다는 점에 유의하라. 따라서 게임이 시작된 지 0.1초 후에는 쿠키를 0.2개 가지게 되고, 게임이 시작된 지 π초 후에는 쿠키를 2π개 가지게 된다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 60초. 1 ≤ C ≤ 500. 1 ≤ F ≤ 4. 1 ≤ X ≤ 2000.

큰 데이터 세트

시간 제한: 120초. 1 ≤ C ≤ 10000. 1 ≤ F ≤ 100. 1 ≤ X ≤ 100000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 공백으로 구분된 실수 세 개 C, F, X가 주어지며, 각각의 의미는 문제 설명의 앞부분에 서술되어 있다.

C, F, X는 각각 적어도 1개의 숫자, 이어서 1개의 소수점, 이어서 1개부터 5개까지의 숫자로 구성된다. 맨 앞에 불필요한 영은 주어지지 않는다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 맛있는 쿠키 X개를 가질 수 있을 때까지 걸리는 최소 초 수이다.

y를 소수점 이하 7자리까지 출력하는 것을 권장하지만, 반드시 그래야 하는 것은 아니다. y가 정답에 충분히 가까우면 정답으로 인정된다. 즉, 절대 오차 또는 상대 오차가 10^{-6} 이내여야 한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참고하라.

Cookie Clicker은 Orteil이 만들었다. Orteil은 Google Code Jam을 지지하지 않으며 이에 관여하지 않았다.