6615번 - 콜라츠 추측 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 427 | 112 | 89 | 31.338% |
문제
콜라츠 추측은 흥미로운 현상이다. 이 법칙은 간단해보이지만, 수학적으로 아직까지 증명되어있지 않은 문제이다. 우리는 이 추측이 옳다고 받아들이겠다.
콜라츠 추측을 설명하면 다음과 같다. 우선 다음과 같은 양의 정수 수열 xi 를 생각하자.
- 만약 xi 가 짝수이면, xi+1=xi/2
- 만약 xi 가 홀수이면, xi+1=3*xi +1 이다.
이제 문제를 보자.
두개의 양의 정수를 준다. 각각의 수에 대해서 콜라츠 추측으로 만든 수열을 생각하자.
각각의 수열을 비교하였을때 처음으로 같은 숫자가 나왔을때 , 각각 몇번째 수열에서 만나는지 구해본다. 문제의 편의를 위해, 이 수열은 1이 나오면 더이상 진행하지 않는다고 하자. ( 1 다음에 나올 수열을 생각하면, 1, 4, 2, 1, 4, 2, 1로 반복되기 때문이다.)
입력
입력은 몇개의 테스트 케이스로 구성된다. 각 테스트 케이스는 두개의 정수 A와 B가 주어진다. ( 1 ≤ A, B ≤ 1,000,000) 마지막 줄은 두개의 0으로 구성된다.
출력
각각의 테스트 케이스마다 다음과 같은 문장을 한줄에 출력한다.
"A needs SA steps, B needs SB steps, they meet at C"
SA와 SB는 A와 B로 수열을 만들고, 처음으로 같은 숫자 C가 나왔을때 각각의 수열에서 몇번째 인지 알려주는 숫자이다.
예제 입력 1
7 8 27 30 0 0
예제 출력 1
7 needs 13 steps, 8 needs 0 steps, they meet at 8 27 needs 95 steps, 30 needs 2 steps, they meet at 46
출처
ICPC > Regionals > Europe > Central European Regional Contest > CTU Open Contest > CTU Open Contest, 2011 B번
- 문제를 번역한 사람: fredhur
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호