2206. Airports

单点时限: 2.0 sec

内存限制: 256 MB

There are $n$ towns with their own airports in the country X. We know the maximal capacities of the airports - the airport in the town $M_i$ can have at most $d_i$ connections with other towns. The task is to design the net of air connections among the towns in such a way that the town $M_i$ has exactly $d_i$ connections with other towns. We assume that connections are two-way and that each pair of towns has at most one connection between them.

Write a program that:

  • reads the number of towns $n$ and the numbers $d_i$,
  • designs the net of air connections in such a way that for every $i$, $1 \le i \le n$, the town $M_i$ has exactly $d_i$ connections with other towns,
  • writes the list of all connections.

We assume that for the given data a solution exists. If there exists more than one solution the program should find only one.


In the first line there is written one integer $n$, $3 \le n \le 500$, which is the number of towns.

In the following $n$ lines there are written positive integers $d_i$ (one integer in each line).


Your program should write all the connections of the created net. The description of each connection consists of two positive integers separated by a single space. These integers are the numbers of two connected towns. Each description should be placed in a separate line. The numbers of towns in a line can be written in an arbitrary order. Similarly, the order of connections is not important.


5 4
4 2
1 2
2 3
6 3
4 6
4 1

5 人解决,12 人已尝试。

6 份提交通过,共有 40 份提交。

8.2 EMB 奖励。

创建: 12 年,2 月前.

修改: 2 年,8 月前.

最后提交: 2 年,8 月前.

来源: POI 1997 II Stage