Degree Set

题意翻译

给你一个长度为 $n$ 的正整数序列 $d_1, d_2, \cdots, d_n$ （ $d_1 < d_2 < \cdots < d_n$ ）。要求你构造一个满足以下条件的无向图： 1. 有恰好 $d_n + 1$ 个点； 2. 没有自环； 3. 没有重边； 4. 总边数不超过 $10^6$ ； 5. 它的度数集合等于 $d$ 。 点从 $1$ 标号至 $d_n + 1$ 。 图的度数序列是一个长度与图的点数相同的数组 $a$ ，其中 $a_i$ 是第 $i$ 个顶点的度数（与其相邻的顶点数）。 图的度数集合是度数序列**排序后去重**的结果。 保证有解，要求输出符合条件的图。 ##### 输入格式 第一行输入一个正整数 $n$ ；第二行输入 $n$ 个正整数，表示**度数集合**。 ##### 输出格式 第一行输出一个正整数 $m$ ，表示边数；接下来 $m$ 行每行输出第 $i$ 条边的两个端点。 感谢@OrangeLee 提供的翻译

题目描述

You are given a sequence of $ n $ positive integers $ d_{1},d_{2},...,d_{n} $ ( $ d_{1}<d_{2}<...<d_{n} $ ). Your task is to construct an undirected graph such that: - there are exactly $ d_{n}+1 $ vertices; - there are no self-loops; - there are no multiple edges; - there are no more than $ 10^{6} $ edges; - its degree set is equal to $ d $ . Vertices should be numbered $ 1 $ through $ (d_{n}+1) $ . Degree sequence is an array $ a $ with length equal to the number of vertices in a graph such that $ a_{i} $ is the number of vertices adjacent to $ i $ -th vertex. Degree set is a sorted in increasing order sequence of all distinct values from the degree sequence. It is guaranteed that there exists such a graph that all the conditions hold, and it contains no more than $ 10^{6} $ edges. Print the resulting graph.

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1<=n<=300 $ ) — the size of the degree set. The second line contains $ n $ integers $ d_{1},d_{2},...,d_{n} $ ( $ 1<=d_{i}<=1000 $ , $ d_{1}<d_{2}<...<d_{n} $ ) — the degree set.

输出格式

In the first line print one integer $ m $ ( $ 1<=m<=10^{6} $ ) — the number of edges in the resulting graph. It is guaranteed that there exists such a graph that all the conditions hold and it contains no more than $ 10^{6} $ edges. Each of the next $ m $ lines should contain two integers $ v_{i} $ and $ u_{i} $ ( $ 1<=v_{i},u_{i}<=d_{n}+1 $ ) — the description of the $ i $ -th edge.

输入输出样例

输入样例 #1

3
2 3 4

输出样例 #1

8
3 1
4 2
4 5
2 5
5 1
3 2
2 1
5 3

输入样例 #2

3
1 2 3

输出样例 #2

4
1 2
1 3
1 4
2 3