D. Degree Set

Codeforces

IDCF976D

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsgraphsimplementation

English · Original

Chinese · Translation

Formal · Original

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 106 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 106 edges. Print the resulting graph. ## Input 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. ## Output In the first line print one integer _m_ (1 ≤ _m_ ≤ 106) — 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 106 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. [samples]

你被给定一个由 #cf_span[n] 个正整数组成的序列 #cf_span[d1, d2, ..., dn] (#cf_span[d1 < d2 < ... < dn])。你的任务是构造一个无向图，满足以下条件：顶点编号应为 #cf_span[1] 到 #cf_span[(dn + 1)]。 _度序列_ 是一个长度等于图中顶点数的数组 #cf_span[a]，其中 #cf_span[ai] 表示与第 #cf_span[i] 个顶点相邻的顶点数。 _度集_ 是将度序列中所有不同值按升序排列得到的序列。保证存在满足所有条件的图，且其边数不超过 #cf_span[106]。请输出构造出的图。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 度集的大小。第二行包含 #cf_span[n] 个整数 #cf_span[d1, d2, ..., dn] (#cf_span[1 ≤ di ≤ 1000], #cf_span[d1 < d2 < ... < dn]) —— 度集。第一行输出一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 106]) —— 构造出的图的边数。保证存在满足所有条件的图，且其边数不超过 #cf_span[106]。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[vi] 和 #cf_span[ui] (#cf_span[1 ≤ vi, ui ≤ dn + 1]) —— 第 #cf_span[i] 条边的描述。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 度集的大小。第二行包含 #cf_span[n] 个整数 #cf_span[d1, d2, ..., dn] (#cf_span[1 ≤ di ≤ 1000], #cf_span[d1 < d2 < ... < dn]) —— 度集。 ## Output 第一行输出一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 106]) —— 构造出的图的边数。保证存在满足所有条件的图，且其边数不超过 #cf_span[106]。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[vi] 和 #cf_span[ui] (#cf_span[1 ≤ vi, ui ≤ dn + 1]) —— 第 #cf_span[i] 条边的描述。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the size of the degree set. Let $ D = (d_1, d_2, \dots, d_n) $ be a strictly increasing sequence of positive integers, $ d_1 < d_2 < \dots < d_n $, representing the degree set. Let $ V = \{1, 2, \dots, d_n + 1\} $ be the vertex set of the undirected graph. Let $ \mathbf{a} = (a_1, a_2, \dots, a_{d_n+1}) \in \mathbb{Z}^{d_n+1} $ be the degree sequence of the graph, where $ a_i $ is the degree of vertex $ i $. Let $ \text{Set}(\mathbf{a}) = \{ a_i \mid i \in V \} $ be the multiset of degrees, and its sorted distinct values equal $ D $: $$ \text{sorted}(\text{distinct}(\mathbf{a})) = D $$ **Constraints** 1. $ 1 \leq n \leq 300 $ 2. $ 1 \leq d_i \leq 1000 $ for all $ i \in \{1, \dots, n\} $ 3. $ d_1 < d_2 < \dots < d_n $ 4. The graph has no more than $ 10^6 $ edges. 5. The degree sequence $ \mathbf{a} $ must contain **exactly** the distinct degrees $ d_1, d_2, \dots, d_n $, and no others. **Objective** Construct an undirected graph $ G = (V, E) $ with vertex set $ V = \{1, 2, \dots, d_n + 1\} $ and edge set $ E \subseteq \binom{V}{2} $, such that: - The set of degrees of vertices in $ G $ is exactly $ D $. - Output the number of edges $ m = |E| $, followed by the $ m $ edges (as unordered pairs $ \{u, v\} $). **Note**: The existence of such a graph is guaranteed.

Samples

Input #1

3
2 3 4

Output #1

Input #2

3
1 2 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Degree Set",
    "description": {
      "content": "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 verti",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF976D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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:\n\n*   there are exactly _d__n_ + 1 verti...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个由 #cf_span[n] 个正整数组成的序列 #cf_span[d1, d2, ..., dn] (#cf_span[d1 < d2 < ... < dn])。你的任务是构造一个无向图，满足以下条件：\n\n顶点编号应为 #cf_span[1] 到 #cf_span[(dn + 1)]。\n\n_度序列_ 是一个长度等于图中顶点数的数组 #cf_span[a]，其中 #cf_span[ai]...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the degree set.  \nLet $ D = (d_1, d_2, \\dots, d_n) $ be a strictly increasing sequence of positive integers, $ d_1 < d_2 < \\dots < d_n $, re...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments