Informatica Online Judge

  평균값 수열 [1221 / 04C5]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 21   Total Tried : 38


The Champion of this Problem (C++) : gs15120 - 196ms / 1465byte
My Best Submission (C++) : N/A

[IOI 2005 - Nowy Sacz, Poland]

Background

길이 n+1의 비감소 수열 S1... Sn+1이 있다. (1 <= i <= n에서 Si <= Si+1)

이러한 수열의 "평균값 수열"을 다음과 같이 정의한다 : 1 <= i <= n에서 Mi = (Si + Si+1)/2.

예를 들어, S = {1,2,2,4} 일 때 M = {3/2,2,3}이다. 이렇듯 평균값 수열은 정수가 아닌 수가 나올 수도 있지만, 이 문제에서는 Mi가 정수인 경우만 고려하기로 한다.

길이 n의 감소하지 않는 평균값 수열 m1 ... mn이 주어질때, 해당 수열을 평균값 수열로 가지는 수열 s1.. sn+1의 개수를 세어라.

Input

첫번째 줄에 평균값 수열의 길이 n이 주어진다.

이후 n개의 줄에 평균값 수열 mi가 순서대로 주어진다.

[입력값의 정의역]
3 <= n <= 5,000,000
0 <= mi <= 1,000,000,000

[Sub-Task Info]
#1 : 3 <= n <= 1,000, 0 <= mi <= 20,000 (50%)
#2 : 추가 제한 조건은 없다. (50%)

Output

주어진 수열을 평균값 수열로 가지는 수열의 개수를 출력하라.

IO Example

입력
3
2
5
9

출력
4

설명
다음과 같은 4가지 경우만이 존재한다 : {2,2,8,10} / {1,3,7,11} / {0,4,6,12} / {-1,5,5,13}

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