ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2008 > задача:


B. Roads

Задачи сборника

• A. Math and Soldiers
• B. Roads
• C. Brackets
• D. Bit Decoder
• E. Points
• F. Division
• G. String Multiplication
• H. Lawyers Council

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.

Long ago the Byteland kingdom had a wide system of roads. Unfortunately, that was a long time ago, and now this system does not exist. Citizens can't even remember, what towns were connected with their own town by roads. The only thing they do remember is the number of roads, that this town once had.
The new king wants to restore the road system and asked you to design the road scheme. You have to find out, what towns should be connected by roads, so that the following requirements are met:

1. From each town where should be a path to any other town, and there cannot be more than one path between two towns.
2. Each town should have the same number of roads it had long time ago. Citizens of each town remember this number.

Get to work, the king does not like to wait!

Input
In the first line an integer number N is written - number of towns in Byteland (2 ≤ N ≤ 10000). In the next N lines follow numbers Ci - number of roads, that i-th town once had (1 ≤ Ci ≤ 10000). All towns are numbered from 1 to N.
Output
If the required road system does not exist, output -1. Otherwise write in first line the number of roads required to be built. In next lines write the road descriptions one per line in arbitrary order. Each road is described by numbers of towns it connects, in increasing order. All roads are two-way. No road can connect a town to itself. Two towns cannot be connected by more than one road. If there are several solutions, output any of them.

Input 1 Output 1 Input 2 Output 2 Input 3 Output 3
2
1
1
1
1 2
3
1
1
1
-1
4
1
1
3
1
3
1 3
2 3
3 4

Для отправки решений необходимо выполнить вход.

www.contester.ru