joi 2010/2011 예선 4- 초등학교 1학년 (초딩) > 문제은행 : 정보올림피아드&알고리즘




2892 : 초등학교 1학년 (초딩)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
5 회   
시도횟수
6 회   

문제

초인이가 초등학교 1학년때 이야기이다. 초인이는 막 배운 덧셈, 뺄셈을 아주 좋아해서, 

숫자가 줄 지어있는 것을 보면 마지막 두 숫자 사이에 "="를 넣고 나머지 숫자 사이에 "+"또는 "- "을 넣어 등식을 만들어 놀곤 했다.
예를 들어 "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 이하의 등식 만 초인이가 확인할 수 있는 올바른 등식이다. 

예를 들어, "8 + 3-2-4-8-7 + 2 + 4 + 0 + 8 = 8"는 적절한 등식이지만,

중간에 나타나는 8 + 3-2-4-8이 음수이므로 초인이는 등식이 정확한지 확인할 수 없어 초인이 입장에서는 올바른 등식이 아니다.

 

입력으로 숫자 열이 주어 졌을 때, 초인이가 만들고 확인할 수있는 올바른 등식의 개수를 구하는 프로그램을 작성하라.

 

입력 예 1의 경우를 살펴보면 아래와 같이 10가지 경우가 나온다.

 

8+3-2-4+8-7-2-4-0+8=8
8+3-2-4+8-7-2-4+0+8=8
8+3+2+4-8-7+2-4-0+8=8
8+3+2+4-8-7+2-4+0+8=8
8+3+2-4+8-7+2+4-0-8=8
8+3+2-4+8-7+2+4+0-8=8
8-3+2+4-8+7+2+4-0-8=8
8-3+2+4-8+7+2+4+0-8=8
8-3+2-4+8+7+2-4-0-8=8
8-3+2-4+8+7+2-4+0-8=8


입력형식

입력 파일은 2 행으로 구성된다. 첫 번째 행에 수열의 개수를 나타내는 정수 N (3 <= N <= 100)이 입력된다. 두 번째 행에는 N개의 0 이상 9 이하의 정수가 공백을 구분하여 입력된다. 주어진 입력 데이터의 60%는 초인이가 만들고 확인할 수있는 올바른 등식의 개수가 2^31-1을 넘지 않는다. 또한 주어진 입력 데이터 모두에서 초인이가 만들고 확인할 수있는 올바른 등식의 개수가 2^63-1을 넘지 않는다.

출력형식

입력에 대하여 초인이가 만들고 확인할 수있는 올바른 등식의 개수를 나타내는 정수를 한 줄로 출력하라.

입력 예

11
8 3 2 4 8 7 2 4 0 8 8

출력 예

10

입력 예

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

출력 예

7069052760


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP