만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

방 번호

면접 대비

시간 제한1초메모리 제한256 MB

요약
A + B = N을 만족하고 두 수에 같은 숫자가 한 번도 겹치지 않으며 앞에 0이 오지 않는 자연수 A, B를 찾아, A가 가장 작은 답을 A + B 꼴로 출력한다.
난이도

보통10점 중 6점

유형
완전 탐색, 수학, 구현, 백트래킹
정답자
아직 제출이 없습니다

문제

택희는 연세동 연세빌딩 NN호로 이사했다. 문 앞에 방 번호를 붙이려고 숫자 스티커 세트를 사 왔는데, 세트에는 0부터 9까지의 숫자가 한 장씩만 들어 있었다. 방 번호에 같은 숫자가 두 번 이상 나오면 그대로 붙일 수 없다.

그래서 택희는 NN을 그대로 붙이는 대신, A+B=NA + B = N인 두 자연수 AA와 BB를 붙이기로 했다. AA와 BB에 쓰인 숫자는 모두 서로 달라야 한다. 즉 0부터 9까지의 숫자는 AA와 BB를 합쳐 많아야 한 번씩 쓸 수 있다. 스티커 모양이 특이해서 6을 뒤집어 9로 쓰는 것도 안 된다. AA와 BB는 앞자리에 0이 붙지 않는 자연수다.

방 번호가 555인 경우를 보자. 123 + 432는 2와 3이 두 번씩 쓰여서 안 되고, 99 + 456도 9가 두 번 쓰여서 안 된다. 512 + 43은 어떤 숫자도 두 번 쓰이지 않으므로 붙일 수 있다. 이렇게 붙일 수 있는 분할은 보통 여러 가지다.

방 번호가 제법 큰 수여서 택희는 AA와 BB를 빠르게 찾지 못한다. 택희를 도와주자.

입력

첫째 줄에 방 번호 NN이 주어진다. (1≤N≤1091 \le N \le 10^9)

출력

조건을 만족하는 AA와 BB가 없으면 첫째 줄에 -1만 출력한다.

있으면 조건을 만족하는 쌍 중에서 AA가 가장 작은 쌍을 골라 A + B 형식으로 출력한다. 즉 AA, 공백, 더하기 기호, 공백, BB를 차례로 쓴다. B=N−AB = N - A로 정해지므로 이 규칙을 만족하는 답은 하나뿐이다.

예제2

  1. 예제 1

    입력
    555
    
    예상 출력
    6 + 549
    
  2. 예제 2

    입력
    2
    
    예상 출력
    -1