Make Numbers

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

요약

네 개의 숫자가 주어질 때, 숫자들을 임의의 묶음과 순서로 이어 붙이고 +, -, ×와 표준 우선순위를 사용해 만들 수 있는 서로 다른 음이 아닌 정수의 개수를 센다.

난이도: 어려움10점 중 8점
유형: 완전 탐색, 구현, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

Peter는 초등학교 수학 교사다. 학생들에게 세 가지 기본 연산인 덧셈 (+), 뺄셈 (−), 곱셈 (×)에 익숙해지도록 하기 위해 간단한 산술 퍼즐을 숙제로 낸다. 퍼즐은 4개의 숫자가 주어지고, 그 4개의 숫자와 세 가지 기본 연산 중 적어도 하나를 사용해 만들 수 있는 음이 아닌 정수를 최대한 많이 만드는 것이다. 예를 들어 숫자 1,1,2,1이 주어지면 표 1과 같이 32개의 음이 아닌 정수를 만들 수 있다.

표 1: 1,1,2,1로 만든 수.


0 = 2 − 1 − 1 × 1	1 = 2 + 1 − 1 − 1	2 = 2 + 1 − 1 × 1	3 = 2 + 1 + 1 − 1	4 = 2 + 1 + 1 × 1	5 = 2 + 1 + 1 + 1	8 = 11 − 2 − 1	9 = 11 − 2 × 1
10 = 12 − 1 − 1	11 = 12 − 1 × 1	12 = 12 + 1 − 1	13 = 12 + 1 × 1	14 = 12 + 1 + 1	19 = 21 − 1 − 1	20 = 21 − 1 × 1	21 = 21 + 1 − 1
22 = 21 + 1 × 1	23 = 21 + 1 + 1	32 = 21 + 11	109 = 111 − 2	111 = 112 − 1	112 = 112 × 1	113 = 112 + 1	120 = 121 − 1
121 = 121 × 1	122 = 121 + 1	132 = 12 × 11	210 = 211 − 1	211 = 211 × 1	212 = 211 + 1	222 = 111 × 2	231 = 21 × 11

학생의 답이 가능한 모든 정수를 포함하는지 확인하기 위해 Peter는 퍼즐에서 만들 수 있는 음이 아닌 정수의 총 개수를 알아야 한다. Peter가 총 개수를 계산할 수 있도록 도와주는 프로그램을 작성하시오.

입력

입력 파일은 한 줄에 공백으로 구분된 4개의 정수를 포함하며, 이는 주어진 숫자를 나타낸다.

출력

만들 수 있는 음이 아닌 정수의 총 개수를 출력한다.

제한

수식은 주어진 4개의 숫자와 {+, −, ×} 중 적어도 하나의 연산을 이어 붙여 구성한다. 주어진 숫자는 {1, 2, 3, . . . 9}의 원소다.
주어진 숫자는 여러 그룹으로 나뉘고, 각 그룹의 숫자는 임의의 순서로 순열을 이루어 하나의 수로 이어 붙인다.
기호 −는 뺄셈 연산자로만 사용할 수 있다.
연산 +와 −는 같은 우선순위를 가진다.
연산 ×는 +와 −보다 우선순위가 높다.
우선순위가 가장 높은 연산을 먼저 계산하고, 우선순위가 같은 연산은 왼쪽에서 오른쪽으로 계산한다.

예제2

예제 1
입력
```
1 1 1 1
```
예상 출력
```
15
```
예제 2
입력
```
1 1 2 1
```
예상 출력
```
32
```