Informatica Online Judge

  초딩 (Tiny) [2208 / 08A0]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 45   Total Tried : 52


The Champion of this Problem (C++) : gs17111 - ms / 319byte
My Best Submission (C++) : N/A

[]

Background

경곽이는 올해 초등학교에 입학한 초딩이다. 이번에 덧셈과 뺄셈을 배운 경곽이는 계산하는 것을 너무나 좋아한다.

경곽이는 숫자들이 나열된 수열만 보면 그 숫자들 사이에 ‘+’와 ‘-’기호를 넣어 등식을 만드는 놀이를 한다.

예를 들어 $8$ $3$ $2$ $4$ $8$ $7$ $2$ $4$ $0$ $8$ $8$ 이 있다면

$8+3-2-4+8-7-2-4-0+8=8$과 같이 만들면서 논다.

경곽이는 등식을 만든 후 각각의 등식이 성립하는지를 계산할 수 있다.

등호("=")는 항상 가장 마지막 원소 앞에만 쓸 수 있다.

하지만 경곽이는 초딩 1학년이기 때문에 음수는 이해할 수 없다.

그리고 $20$을 초과하는 수에 대해서도 더 이상 계산할 수 없다.

따라서 계산 중간의 결과가 $0$이상 $20$이하인 경우로 구성된 등식에 대해서만 성립여부를 판단할 수 있다.

입력된 수열을 이용해 경곽이가 만들 수 있는 모든 등식의 개수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 수열의 길이를 나타내는 정수 n이 입력된다.
두 번째 줄에는 0이상 9이하의 정수가 n개 주어진다. 단 정수들은 공백으로 구분되어 있다.

[입력값의 정의역]
$3 <= n <= 15$

Output

경곽이가 확인할 수 있는 올바른 등식의 모든 경우의 수를 출력한다.

IO Example

입력
11
8 3 2 4 8 7 2 4 0 8 8

출력
10

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]