DMOPC '19 Contest 7 P2 - Dinner Party

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Serena has arranged for herself and her family members to come together for dinner at your restaurant! You have arranged the N members of the family, which includes Serena herself, to sit around a circular table. Conveniently, the family members are numbed from 0 to N-1, and sit in such a way that the i-th family member sits adjacent to the [(i-1) \bmod N]-th and [(i+1) \bmod N]-th family member. Having prepared well in advance, you know that the i-th family member would like to be served a total of exactly a_i dishes. Now, the task that remains is to serve the dishes to Serena's family. To do so, you send a waiter out every minute to serve one dish to exactly two adjacent members around the table.

Determine a sequence of operations to satisfy Serena's family, or gingerly tell them that it is not possible to do so.

Input Specification

The first line contains the integer N, the size of Serena's family.
The next line contains N integers a_0, a_1, \dots, a_{N-1}, the number of dishes that are to be served to each family member.

Output Specification

If it is possible to satisfy Serena's family, output YES on a single line. Then, output the integer M, the time required in minutes, on a single line. Then, output M lines, each containing two spaced-separated integers x and y (x \neq y, x adjacent to y, 0 \leq x, y < N). The j-th of these M lines denotes that a waiter should serve the x-th and the y-th family member simultaneously on the j-th minute.

Otherwise, output NO on a single line.


3 \leq N \leq 1\,000\,000
0 \leq a_i \leq 1\,000\,000
The sum of all a_i does not exceed 1\,000\,000.

Sample Input 1

3 2 2 0 3

Sample Output 1

0 4
4 0
1 2
1 2
4 0

Sample Input 2

1337 1337 1337

Sample Output 2



There are no comments at the moment.