## IOI '05 P2 - Mean Sequence

View as PDF

Points: 12 (partial)
Time limit: 2.5s
Memory limit: 16M

Problem type

Consider a nondecreasing sequence of integers ( for ). The sequence defined by , for , is called the mean sequence of sequence . For example, the mean sequence of sequence is the sequence . 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 integers , compute the number of nondecreasing sequences of integers that have the given sequence as mean sequence.

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.

#### Input

The first line of the standard input contains one integer . The remaining lines contain the sequence . Line contains a single integer . You can assume that in of the test cases and .

#### Output

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

#### Explanation for Sample Output

Indeed, there are four nondecreasing integer sequences for which is the mean sequence. These sequences are:

• ,
• ,
• ,
• .