암호화 함수

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

요약

숫자의 모든 자리 부분집합을 수로 해석해 더하는 암호화 함수의 출력이 주어질 때, 그 값이 나오는 원래 수를 찾거나 존재하지 않으면 NIE를 출력한다.

난이도: 어려움10점 중 8점
유형: 수학, 동적 계획법, 완전 탐색, 정수론
정답자: 아직 제출이 없습니다

문제

컴퓨터 수업을 들은 Sophie는 숫자를 입력으로 받는 자신만의 암호화 함수를 만들었다. 이 함수는 입력받은 수를 앞에 0이 없는 십진수 자릿수의 나열로 보고, 그 나열에서 가능한 모든 위치의 부분집합을 골라 가린 뒤, 새로 얻은 나열을 십진수(앞에 0이 붙을 수도 있다)로 해석하고, 이렇게 얻은 모든 수를 더한다. Sophie는 아직 복호화 알고리즘을 만들지 못했다. 그녀를 도와 암호화된 수를 복호화하는 프로그램을 작성하라.

입력

입력은 양의 정수 $n$ 하나로 이루어진다( $1 \le n \le 10^{18}$ ). $n$ 은 Sophie의 암호화 함수의 출력이다.

출력

첫째 줄이자 유일한 줄에, 암호화한 값이 $n$ 이 되는 양의 정수 $m$ 을 출력하라. 그러한 수가 없으면 NIE(폴란드어로 '아니오')를 출력한다.

답이 여러 개라면 아무거나 하나 출력해도 된다.

힌트

예제 1에서 $123$ 에 암호화 함수를 적용한 값은 $1 + 2 + 3 + 12 + 13 + 23 + 123 = 177$ 이다.

예제 2에서 암호화한 값이 $42$ 가 되는 수는 없다.

예제2

예제 1
입력
```
177
```
예상 출력
```
123
```
예제 2
입력
```
42
```
예상 출력
```
NIE
```