305123: CF976D. Degree Set

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给你一个长度为 $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 提供的翻译

加入题单

上一题 下一题 算法标签: