금고 번호 바꾸기
문제
어느 금고에는 자연수 하나가 번호로 걸려 있다. 지금 걸려 있는 번호는 A이고, 금고의 주인은 이 번호를 B로 바꾸려 한다.
번호를 한 번 바꿀 때 쓸 수 있는 조작은 다음의 두 가지뿐이다.
1) 지금 걸린 번호를 두 배로 만든다.
2) 지금 걸린 번호의 오른쪽 끝에 숫자 1을 하나 덧붙인다.
금고는 번호가 바뀔 때마다 바뀐 뒤의 번호를 기록부에 한 줄씩 적는다. 기록부의 첫 줄에는 처음 걸려 있던 A가 적혀 있다. 따라서 번호를 B까지 바꾸고 나면 기록부에는 A로 시작해 B로 끝나는 번호들이 차례대로 남는다.
금고의 주인은 기록부에 남는 줄의 수를 되도록 적게 하려 한다. 결과적으로 A와 B가 주어졌을 때, 기록부에 남는 줄의 최소 개수를 구하는 프로그램을 작성하여라. 두 조작만으로는 A를 B로 바꿀 수 없다면 -1을 출력한다.
예를 들어 A=2이고 B=162라고 해보자. 2를 두 배로 만들어 4, 다시 두 배로 만들어 8, 오른쪽에 1을 붙여 81, 마지막으로 두 배로 만들어 162를 얻을 수 있다. 이 과정을 정리하면 다음과 같다.
| 기록부의 줄 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 적힌 번호 | 2 | 4 | 8 | 81 | 162 |
| 쓴 조작 | 두 배 | 두 배 | 1 붙이기 | 두 배 |
기록부에 남는 줄은 모두 5개다. 이보다 적은 줄로 162를 얻는 방법은 없으므로 이 경우 정답은 5이다.
한편 A=4이고 B=42인 경우를 보자. 4에서 쓸 수 있는 조작은 두 배인 8과 1을 붙인 41뿐이고, 8에서는 16과 81이, 41에서는 82와 411이 나온다. 두 조작은 번호를 늘리기만 하므로 한 번 42를 지나치고 나면 다시 42로 되돌아올 길이 없다. 결국 어느 길로 가도 42가 나오지 않으므로 이 경우 정답은 -1이다.
입출력 예시
예시 1
입력
2 162
출력
5
예시 2
입력
123 2461
출력
3
예시 3
입력
4 42
출력
-1
입력 조건
가장 먼저 금고에 지금 걸려 있는 번호 A와 바꾸려는 번호 B가 공백 하나로 구분되어 한 줄에 주어진다. A와 B는 각각 1 이상 1,000,000,000 이하의 자연수이며, A는 B보다 작거나 같다. 두 수가 서로 같은 경우도 주어질 수 있다. 입력은 이 한 줄로 끝나며, 다른 줄은 주어지지 않는다.
출력 조건
기록부에 남는 줄의 최소 개수를 한 줄에 출력한다. 처음의 A와 마지막의 B도 한 줄씩으로 세며, A와 B가 서로 같다면 1을 출력한다. 두 조작만으로 A를 B로 바꿀 수 없다면 -1을 출력한다. 수 하나만 출력하므로 줄 끝에 남기는 공백은 없다.
요구사항
- 조작은 두 배로 만들기와 오른쪽에 1 붙이기 두 가지뿐입니다
- 답은 조작 횟수가 아니라 기록부에 남는 줄의 개수입니다. 처음의 A와 마지막의 B도 한 줄씩으로 셉니다
- A와 B가 같다면 조작을 한 번도 하지 않으므로 답은 1입니다
- 두 조작은 번호를 늘리기만 하므로 B를 지나친 번호에서는 되돌아올 수 없습니다
- 바꿀 수 없다면 -1을 출력합니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
2 162
5
4 42
-1
123 2461
3
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.