DMOPC '18 Contest 4 P6 - Dr. Henri and Resistor Chains

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Dr. Henri is trying to create a particular circuit. This circuit forms the edges of an N by 1 grid of cells so that a resistor lies across each edge of the grid, except for the rightmost edge which is a power source. For example, when N=3, the schematic is:

Dr. Henri's latest creation

He already has his power source ready. Now, he must construct the rest of the circuit.

Dr. Henri uses resistor chains. A resistor chain of length i is a chain of i resistors. A chain of length 1 is simply a single resistor. He can bend a chain between its resistors, but he cannot split a chain. Dr. Henri has M resistor chains of length a_1, a_2, \dots, a_M and would like to use all of them in his circuit, so that there are no overlaps. For example, if N=3, M=4 and the lengths are 3, 2, 3, 1, he can construct his circuit like so:

It lives!

Can you help Dr. Henri build his circuit?


1 \le a_i \le 1\,000\,000 for all 1 \le i \le M

Subtask 1 [10%]

1 \le N \le 3
1 \le M \le 10

Subtask 2 [20%]

1 \le N \le 100\,000
1 \le M \le 100\,000
1 \le a_i \le 2

Subtask 3 [30%]

1 \le N \le 100\,000
1 \le M \le 100\,000
a_i \ne 1

Subtask 4 [40%]

1 \le N \le 100\,000
1 \le M \le 100\,000

Input Specification

The first line contains two space-separated integers, N and M.
The next line contains M space-separated integers, a_1, a_2, \dots, a_M.

Output Specification

On a single line, output yes if Dr. Henri can build it given his chains and no otherwise.
If he can build it, output 3 following lines, each with N integers. The first line represents the top row of edges in the circuit, the second line represents the middle row (not including the power source), and the third line represents the bottom row. The integer denotes which chain is being used for that edge. The chains are labelled based on their order in the input (from 1 to M).

Sample Input 1

2 3
4 1 1

Sample Output 1

1 2
1 1
1 3

Explanation for Sample 1

Boring boring boring boring square

Sample Input 2

2 4
4 1 1 1

Sample Output 2


Explanation for Sample 2

Dr. Henri can make his circuit with the first three chains, but he wants to use all four.

Sample Input 3

3 4
3 2 3 1

Sample Output 3

1 1 3
1 2 3
2 3 4


There are no comments at the moment.