프로그램 명: ioi_mea
제한시간: 5 초
//번역//
Consider a nondecreasing sequence of integers s1, . . . , sn+1 (si si+1 for 1 i n). The sequence m1, . . . ,mn
defined by mi = 1
2 (si+si+1), for 1 in, is called the mean sequence of sequence s1, . . . , sn+1. For example,
the mean sequence of sequence 1, 2, 2, 4 is the sequence 1.5, 2, 3. Note that elements of the mean sequence
can be fractions. However, this task deals with mean sequences whose elements are integers only.
Given a nondecreasing sequence of n integers m1, . . . ,mn, compute the number of nondecreasing sequences
of n+1 integers s1, . . . , sn+1 that have the given sequence m1, . . . ,mn as mean sequence.
task
Write a program that:
-
. reads from the standard input a nondecreasing sequence of integers,
-
. calculates the number of nondecreasing sequences, for which the given sequence is mean sequence,
-
. writes the answer to the standard output.
입력
The first line of the standard input contains one integer n (2 n 5000000). The remaining n lines contain
the sequence m1, . . . ,mn. Line i+1 contains a single integer mi (0 mi 1000000000). You can assume
that in 50% of the test cases n 1000 and 0 mi 20000.
출력
Your program should write to the standard output exactly one integer.the number of nondecreasing integer
sequences, that have the input sequence as the mean sequence.
입출력 예
입력
3
2
5
9
출력
4
Indeed, there are four nondecreasing integer sequences for which 2,5,9 is the mean sequence. These sequences
are:
-
2,2,8,10
-
1,3,7,11
-
0,4,6,12
-
-1,5,5,13
출처: IOI'2005
[질/답]
[제출 현황]
[푼 후(2)]