2695번 - 공 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 249 | 141 | 111 | 61.667% |
문제
고전적인 '두 개의 유리 공' 문제는 다음과 같다:
두 개의 동일한 유리구가 있고, 100층 짜리 빌딩에서 유리구를 떨어뜨려서 깨지는 가장 낮은 층을 찾고 싶다. 유리구가 안깨진다면 아무런 피해가 없다고 가정하자. 어떻게 해야 (최악의 상황에서도) 가장 빨리 찾을 수 있을까?
우리가 오직 하나의 공이 있다고 가정하자. 그러면 우리는 1층부터 100층까지 차례대로 떨어뜨려보는 방법 밖에 없다.
최악의 경우는 100번만에 찾는 것이다.
이제 우리에게 두 개의 공이 있다고 하자. 그리고 첫 번째 공을 n층에서 떨어뜨린다고 하자. 만약에 그게 깨진다면 다시 공 하나가 있는 경우로 돌아가서, 1층부터 n-1층까지 시도해보면된다. 이 경우 최악의 경우 1+(n-1), 즉 n번의 시도만에 찾을 수 있다. 하지만 n층에서 깨지지 않았다면, n+1층에서 100층까지만 실험해보면 된다. 깨지거나 깨지지 않았거나 우리는 한 번의 시도를 하였다. 그래서 모든 n에 대한 최솟값이 최악의 경우 필요한 실험 횟수이다.
B개의 공과 M층 짜리 빌딩에서 최악의 경우에 몇 번 공을 떨어뜨려야 하는지를 계산하는 프로그램을 작성하시오.
입력
첫째 줄은 데이터 세트 수 P(1 ≤ P ≤ 1000)가 입력으로 들어온다. 각각의 데이터 세트는 한 줄로 구성되어 있으며 2개의 숫자가 공백으로 구분되어 있다. 유리공의 개수 B(1 ≤ B ≤ 50), 건물의 층 수 M(1 ≤ M ≤ 1000)
출력
각각의 데이터 세트에 대해 한 줄 씩, B, M에 대해 (최악의 경우에도)가장 적은 횟수의 시도 횟수를 공백으로 구분하여 출력한다.
예제 입력 1
4 2 10 2 100 2 300 25 900
예제 출력 1
4 14 24 10
출처
ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest C번
- 문제를 번역한 사람: exupery
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호