부하 테스트 (라지)
시간 제한5초메모리 제한512 MB
동작하는 부하 L과 실패하는 부하 P가 주어질 때 C배 이내로 용량을 확정하는 적응형 테스트 횟수의 최악값을 구합니다.
문제
프로그래밍 대회 웹사이트를 운영한다. 내년 대회에는 참가자가 P명 모일 것으로 예상되므로 사이트가 그만큼의 인원을 동시에 받아내야 한다.
지난 대회에서 이 사이트가 적어도 L명까지는 오류 없이 동시에 처리한다는 사실을 확인했다. 또 P명은 처리하지 못한다는 사실도 알고 있다.
사이트의 실제 처리 한계를 C배 이내로 좁히려고 한다. 즉 사이트가 a명은 처리하고 a * C명은 처리하지 못한다는 것을 아는 정수 a를 찾으면 된다.
부하 테스트를 여러 번 실행할 수 있다. 한 번의 부하 테스트는 정수 X를 골라 사이트가 X명 이상을 처리하는지 알려준다. 앞선 테스트 결과를 보고 다음에 시험할 값을 정할 수 있다. 최적으로 선택할 때 최악의 경우 부하 테스트를 몇 번 해야 하는가?
입력
첫 줄에 테스트 케이스 수 T가 주어진다. 이어지는 T개의 줄에 정수 L, P, C가 순서대로 공백으로 구분되어 주어진다.
제한
- L, P, C는 모두 정수다
출력
각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 케이스 번호이고, y는 처리 한계를 C배 이내로 좁히기까지 최악의 경우 필요한 부하 테스트 횟수다.
힌트
첫 번째 예제의 두 번째 케이스에서는 사이트가 19명은 처리하고 57명은 처리하지 못한다는 사실을 이미 알고 있다. 두 값의 비가 정확히 3배이므로 테스트가 필요 없다.
네 번째 케이스에서 48을 시험한다고 하자. 사이트가 48명을 처리하면 48 * 2 < 97이므로 아직 더 시험해야 한다. 대신 49를 시험해서 처리하지 못한다는 답을 받아도 24 * 2 < 49이므로 더 시험해야 한다. 테스트 두 번이면 충분하다.