단추 네 개로 수 만들기
문제
박물관에 전시된 낡은 계산기에는 단추가 네 개뿐이다. 화면에는 수 하나가 떠 있고, 어떤 단추를 누르든 화면의 수를 자기 자신과 계산해서 그 결과를 다시 화면에 띄운다. 화면의 수가 X일 때 네 단추가 하는 일은 다음의 표와 같다.
| 단추 | 글자 | 누른 뒤 화면의 수 |
|---|---|---|
| 곱하기 | "*" | X를 제곱한 값 |
| 더하기 | "+" | X를 두 배로 한 값 |
| 빼기 | "-" | X에서 X를 뺀 값이라서 항상 0 |
| 나누기 | "/" | X를 X로 나눈 값이라서 항상 1 |
나누기 단추는 화면의 수가 0일 때는 쓸 수 없다. 또한 화면에 띄울 수 있는 수는 1,000,000,000 이하다. 어떤 단추를 눌러 1,000,000,000보다 큰 수가 화면에 뜨면 그 뒤로는 단추를 더 누를 수 없고, 그 상태에서는 목표를 이룰 수도 없다. 예를 들어 화면의 수가 100,000일 때 곱하기 단추를 누르면 10,000,000,000이 되어 한도를 넘으므로, 그 자리에서 더 해 볼 것이 없다.
처음 화면에 떠 있는 수는 s이고, 화면에 t를 띄우는 것이 목표다. 누르는 횟수가 가장 적은 방법이 여러 가지일 수도 있다. 그런 경우에는 단추의 글자를 "*", "+", "-", "/"의 순서로 앞선 것으로 보고 사전 순으로 가장 앞서는 하나를 답으로 삼는다. 즉 같은 횟수로 목표를 이루는 방법이 곱하기 뒤에 더하기인 경우와 더하기 뒤에 곱하기인 경우로 둘 다 있다면, 앞쪽 글자가 더 앞선 쪽을 답으로 삼는다.
단추를 누르는 횟수를 최소로 하고, 그때 누른 단추를 순서대로 적어서 출력하는 프로그램을 작성하여라.
예를 들어 s=12이고 t=2라고 해보자. 나누기 단추를 누르면 12를 12로 나눈 1이 화면에 뜨고, 이어서 더하기 단추를 누르면 1을 두 배로 한 2가 화면에 뜬다.
| 누른 횟수 | 0 | 1 | 2 |
|---|---|---|---|
| 누른 단추 | 없음 | 나누기 | 더하기 |
| 화면의 수 | 12 | 1 | 2 |
단추를 한 번만 눌러서 2를 띄우는 방법은 없다. 12를 제곱하면 144이고, 두 배로 하면 24이며, 빼기는 0이고 나누기는 1이다. 따라서 이 예시에서의 답은 누른 단추의 글자를 순서대로 이어 붙인 "/+"이다.
입출력 예시
예시 1
입력
12 2
출력
/+
예시 2
입력
2 2
출력
0
예시 3
입력
3 0
출력
-
예시 4
입력
5 125
출력
-1
입력 조건
가장 먼저 처음 화면에 떠 있는 수 s와 목표로 하는 수 t가 한 줄에 공백으로 구분되어 주어진다. s는 1 이상 1,000,000,000 이하의 자연수이므로 처음 화면에 0이 뜨는 일은 없다. t는 0 이상 1,000,000,000 이하의 정수이며, 빼기 단추로 0을 띄울 수 있으므로 t가 0으로 주어질 수 있다. 두 수가 서로 같을 수도 있다. 입력은 이 한 줄로 끝난다.
출력 조건
단추를 누르는 횟수가 최소가 되도록 눌렀을 때, 누른 단추의 글자를 순서대로 띄어쓰기 없이 이어 붙여 한 줄에 출력한다. 누르는 횟수가 가장 적은 방법이 여러 가지라면, 단추의 글자를 "*", "+", "-", "/"의 순서로 앞선 것으로 보아 사전 순으로 가장 앞서는 것을 출력한다.
s와 t가 같아서 단추를 누를 필요가 없다면 0을 출력한다. 어떻게 눌러도 t를 띄울 수 없다면 -1을 출력한다.
요구사항
- 단추는 화면의 수를 자기 자신과 계산하므로 다른 수를 넣을 수 없습니다
- 나누기 단추는 화면의 수가 0일 때 쓸 수 없습니다
- 1,000,000,000보다 큰 수가 화면에 뜨면 그 뒤로는 단추를 누를 수 없습니다
- 누르는 횟수가 가장 적은 방법이 여러 가지면 사전 순으로 가장 앞서는 것을 출력합니다
- 누를 필요가 없으면 0을, 만들 수 없으면 -1을 출력합니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 4개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 4개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
12 2
/+
2 2
0
5 125
-1
3 0
-
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 4개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.