올바른 식

면접 대비

시간 제한2초메모리 제한1024 MB

요약

큰 정수로 이루어진 식 A ? B = C가 성립하는 2진법부터 10진법까지의 진법을 모두 구합니다.

난이도: 쉬움10점 중 3점
유형: 완전 탐색, 구현, 수학
정답자: 아직 제출이 없습니다

문제

언뜻 보면 거짓처럼 보이는 등식이 있습니다. 예를 들어 $2 + 2 = 11$ 은 거짓처럼 보이지만, 밑이 $3$ 인 진법에서는 참이 됩니다: $2_3+2_3=11_3=4_{10}$ .

$A ? B = C$ 꼴의 식이 주어집니다. 여기서 $A$ , $B$ , $C$ 는 음이 아닌 정수이고, $?$ 는 덧셈, 뺄셈, 곱셈 중 하나의 기호입니다. $2$ 부터 $10$ 까지의 진법 중에서 이 등식이 참이 되는 밑을 모두 구하세요. 밑이 $n$ 인 진법은 숫자 $0$ 부터 $n-1$ 까지만 사용한다는 점에 유의하세요.

입력

입력은 $A ? B = C$ 식이 적힌 한 줄입니다. $?$ 자리에는 $+$ , $-$ , $*$ 중 하나가 옵니다. 식의 각 부분은 공백 한 칸으로 구분됩니다. $A$ , $B$ , $C$ 의 자릿수는 각각 1000 이하입니다. 각 수는 숫자 0부터 9로만 이루어지며, 불필요한 앞자리 0은 없습니다.

출력

첫 줄에 조건을 만족하는 밑의 개수 $k$ 를 출력합니다. 둘째 줄에는 그 $k$ 개의 밑을 오름차순으로 출력합니다.

예제3

예제 1
입력
```
2 + 2 = 11
```
예상 출력
```
1
3
```
예제 2
입력
```
2 + 2 = 4
```
예상 출력
```
6
5 6 7 8 9 10
```
예제 3
입력
```
2 * 2 = 5
```
예상 출력
```
0
```