DMOPC '21 Contest 9 P1 - Board Numbers

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

You wrote your favourite N positive integers on the board and then wrote the N-1 adjacent sums too. Someone erased your integers, but not your sums. Instead of being mad, you became quite curious: how many arrays of N numbers could generate these sums?

That is, given an array of adjacent sums, how many arrays of positive integers generate these sums?


2 \le N \le 10^6

1 \le a_i \le 10^9

Subtask 1 [10%]

N = 2

Subtask 2 [30%]

N = 3

Subtask 3 [30%]

1 \le a_i \le 10

Subtask 4 [30%]

No additional constraints.

Input Specification

The first line contains the integer N.

The next line contains N - 1 space-separated integers a_i, the adjacent sums on the board.

Output Specification

Output the number of arrays of positive integers that could yield a_i. If there is a mistake and no valid array exists, output 0.

Sample Input

5 4 3

Sample Output



The two arrays are 2 3 1 2 and 3 2 2 1.


There are no comments at the moment.