Izrazi

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

요약

길이 15 이하의 숫자 문자열에서 더하기, 빼기, 곱하기를 각각 한 번 이하로 넣어 만들 수 있는 서로 다른 음이 아닌 결과의 개수를 센다.

난이도: 보통10점 중 7점
유형: 분할 정복, 완전 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

Neka je zadan string sastavljen samo od znamenki i to ne više od $15$ njih. Od zadanog stringa, ne mijenjajući poredak znamenki u njemu, kreiraj aritmetički izraz dodajući operatore između znamenki. Pri kreiranju izraza treba poštovati sljedeća pravila:

Od operatora smiju se koristiti samo operator zbrajanja (+), oduzimanja (-) i množenja (*);
svaki se operator smije iskoristit jednom ili nijednom;
u string se mora dodati najmanje jedan operator;
broj u izrazu (operand) ne smije početi nulom, osim ako je nula;
rezultat tako dobivenog izraza mora biti nenegativan.

Napiši program koji će za zadani string odrediti koliko različitih rezultata možemo dobiti kreiranjem izraza na opisani način.

입력

U prvom je retku string $S$ iz teksta zadatka.

출력

U prvi redak ispiši cijeli broj iz teksta zadatka.

힌트

Opis prvog probnog primjera: Zadan je string “1504”. Od tog stringa, dodavanje operatora +, - i * možemo dobiti $18$ valjanih izraza. Uoči da se rezultat $15$ pojavljuje dva puta.

1+504 = 505
150+4 = 154
150-4 = 146
1*504 = 504
150*4 = 600
15-0+4 = 19
15-0*4 = 15
1+50-4 = 47
15+0-4 = 11
1+50*4 = 201
15+0*4 = 15
1*50-4 = 46
1*50+4 = 54
15*0+4 = 4
1+5-0*4 = 6
1*5+0-4 = 1
1*5-0+4 = 9
1-5*0+4 = 5

예제3

예제 1
입력
```
1504
```
예상 출력
```
17
```
예제 2
입력
```
1200032
```
예상 출력
```
42
```
예제 3
입력
```
987654
```
예상 출력
```
100
```