DMOPC '21 Contest 9 P1 - Board Numbers - DMOJ: Modern Online Judge

DMOPC '21 Contest 9 P1 - Board Numbers

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

You wrote your favourite $N$ $N$ positive integers on the board and then wrote the $N-1$ $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$ $N$ numbers could generate these sums?

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

Constraints

$2 \le N \le 10^6$ $2 \leq N \leq 10^{6}$

$1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$

Subtask 1 [10%]

$N = 2$ $N = 2$

Subtask 2 [30%]

$N = 3$ $N = 3$

Subtask 3 [30%]

$1 \le a_i \le 10$ $1 \leq a_{i} \leq 10$

Subtask 4 [30%]

No additional constraints.

Input Specification

The first line contains the integer $N$ $N$ .

The next line contains $N - 1$ $N - 1$ space-separated integers $a_i$ $a_{i}$ , the adjacent sums on the board.

Output Specification

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

Sample Input

Copy

4
5 4 3

Sample Output

Copy

Explanation

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

Comments

1
Nick_Lomov commented on Oct. 31, 2024, 7:24 p.m.
For those unsure what adjacent sums mean, here's an example:

Copy
Original array: 1 2 3 4 Adjacent sums array: 3 5 7

So 3=1+2, 5=2+3, etc.

In this problem, you're given the adjacent sums array and have to figure out the number of possibilities for the original array.