4연산

s에서 시작해 +, -, *, / 연산(s+s, s-s, s*s, s/s)만으로 t에 도달하는 최소 연산 순서를 찾고, 같은 길이면 사전순으로 가장 앞선 답을 출력한다.

보통5BFS수학완전 탐색아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

정수 ss가 주어진다. ss의 값을 tt로 바꾸는 데 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

  1. s = s + s; (출력: +)
  2. s = s - s; (출력: -)
  3. s = s * s; (출력: *)
  4. s = s / s; (출력: /) (ss가 0이 아닐 때만 사용할 수 있다)

입력

첫째 줄에 두 정수 sstt가 공백으로 구분되어 주어진다. (1s,t1091 \le s, t \le 10^9)

출력

첫째 줄에 sstt로 바꾸는 방법을, 사용한 연산의 출력 문자를 순서대로 이어 붙인 문자열로 출력한다. 연산 횟수가 최소인 방법만 답이 된다. sstt가 같으면 0을, 바꿀 수 없으면 -1을 출력한다.

최소 횟수로 바꾸는 방법이 여러 가지라면 사전 순으로 가장 앞서는 것을 출력한다. 연산 문자의 아스키 코드 순서는 *, +, -, /이다.