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