프로그램 명: balls
제한시간: 1 초

고전적인 "두개의 유리공"이라는 어렵지만 재미있는 문제는 종종 이렇게 알려져 있다.

"두개의 똑같은 유리공이 주어졌을 때, 100층 건물의 어느 곳이 유리공을 떨어트렸을 때 깨지는 가장 낮은 층인지 알고 싶다. 깨지는 가장 낮은 층 아래에서 유리공을 떨어트릴 때는 깨지지 않는다고 추정하자. 가장 안좋은 경우에 떨어트리는 회수를 최소화 할 수 있는 전략은 무엇인가?"

한개의 유리공을 가지고 있다고 생각하자. 우리는 1층부터 100층까지 연속적으로 각층에서 떨어트려 볼 수 있다. 이때 최악의 경우엔 100번을 떨어트려 봐야 한다.

이제 두개의 유리공을 가지고 있는 경우를 고려해보자. 첫번째 유리공을 n층에서 떨어트린다고 생각해보자. 만약에 떨어트린 유리공이 깨진다면 우리는 한개의 공만 가지고 있게 되고, 1층부터 n-1층까지 차례대로 나머지 공을 떨어트려야 한다. 최악의 경우에 떨어트리는 회수는 n번이 된다. (첫번째 공이 한번 떨어졌고, 두번째 공이 n-1번 떨어졌다).

그러나 만약 첫번째 공을 n층에서 떨어트릴 때 깨지지 않았다면 n+1층부터 100층까지의 문제로 줄게 된다. 여하간에 우리는 이미 한번 떨어트렸다는 사실을 기억해야 한다. 그렇게 최악의 경우의 떨어트리는 회수의 최소값은 모든 n층에 걸쳐서의 최소값이다.

당신은 B개의 유리공과 M층의 빌딩이 주어졌을 때 최악의 경우에 떨어트리는 횟수의 최소값을 측정하는 프로그램을 작성해야 한다.

입력

입력의 첫번째 줄은 총 데이터 세트의 개수를 나타내는 하나의 정수 P (1 ≤ P ≤ 1000) 를 포함하고 있다. 각각의 데이터 세트는 3개의 정수[문제 번호, 공백, 유리공의 개수 B(1 ≤ B ≤ 50), 공백, 빌딩의 층수 M(1 ≤ M ≤ 1000)] 로된 한개의 줄로 구성되어 있다.

출력

각각의 데이터 세트에 대하여 다음과 같은 한줄의 출력 결과를 생성하라. 데이터세트의 번호, 공백, B와 M값에 해당하는 최소 낙하 횟수.

입출력 예

입력

4
1 2 10
2 2 100
3 2 300
4 25 900

출력

1 4
2 14
3 24
4 10

출처:Greater new york 2009
번역:makecode
[질/답] [제출 현황] [푼 후(1)]
[ 채 점 ] [홈으로]  [뒤 로]