시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 16 MB 143 39 33 25.000%

문제

길이 n+1의 비감소 수열 s1,...,sn+1 (si ≤ si+1 for 1 ≤ i ≤ n) 을 생각해보자.

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

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

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

입력

첫번째 줄에 평균값 수열의 길이 n이 주어진다. (2 <= n <= 5,000,000)

이후 n개의 줄에 평균값 수열 mi가 순서대로 주어진다. (0 <= mi <= 1,000,000,000)

출력

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

예제 입력

3
2
5
9

예제 출력

4

힌트

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

출처

Olympiad > International Olympiad in Informatics > IOI 2005 2번

  • 문제를 번역한 사람: koosaga