cf Educational Codeforces Round 43 D. Degree Set

原題：

D. Degree Set

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

You are given a sequence of n positive integers d1, d2, …, dn (d1 < d2 < … < dn). Your task is to construct an undirected graph such that:

there are exactly dn + 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 (dn + 1).

Degree sequence is an array a with length equal to the number of vertices in a graph such that ai 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.

Input

The first line contains one integer n (1 ≤ n ≤ 300) — the size of the degree set.

The second line contains n integers d1, d2, …, dn (1 ≤ di ≤ 1000, d1 < d2 < … < dn) — 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 vi and ui (1 ≤ vi, ui ≤ dn + 1) — the description of the i-th edge.

Examples

input

3

2 3 4

output

8

3 1

4 2

4 5

2 5

5 1

3 2

2 1

5 3

input

3

1 2 3

output

4

1 2

1 3

1 4

2 3

中文：

有一個圖，這個圖中所有節點的度為d1,d2,…dn，從小到大。

這個圖沒有重邊，沒有定點上的邊連接配接該定點自己，一共dn+1個定點，邊數不超過10^6。

現在讓你找出這麼樣的一個圖來，滿足上面的條件。

代碼：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;


struct node
{
    int f,t;
};

int n;
deque<int> G;

deque<node> dfs(int x,deque<int> g)
{
    deque<node> v;
    if(g.empty())
        return v;
    for(int i=;i<g.front();i++)
    {
        for(int j=x+i+;j<=x+g.back();j++)
        {
            v.push_back(node{x+i,j});
        }
    }
    for(int i=;i<g.size();i++)
        g[i]-=g[];

    int ind= x+g.front();
    g.pop_front();
    if(!g.empty())
        g.pop_back();

    deque<node> res=dfs(ind,g);
    for(int i=;i<res.size();i++)
        v.push_back(res[i]);

    return v;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        G.clear();
        int res;
        for(int i=;i<n;i++)
        {
            cin>>res;
            G.push_back(res);
        }
        deque<node> ans=dfs(,G);
        cout<<ans.size()<<endl;
        for(int i=;i<ans.size();i++)
            cout<<ans[i].f+<<" "<<ans[i].t+<<endl;

    }
    return ;
}
           

思路：

這題很難想，看了題解，感覺構造的方式很巧妙的。

由于有 dn+1 d n + 1 個節點，那麼度為 dn d n 的節點一定是用邊連接配接上了所有的節點。

這裡如下構造：

第一步：找出 d1 d 1 個節點連接配接所有的節點，那麼目前的圖中會有兩個度的值，分别是 d1 d 1 和 dn d n ，度為 dn d n 的節點有 d1 d 1 個，度為 d1 d 1 的節點有 dn+1−d1 d n + 1 − d 1 個。

第二步：将 d2 d 2 到 dn−1 d n − 1 之間的度，全部都減去 d1 d 1 ，其目的是要在第一步中構造的圖中，擷取一個子圖，這個子圖同樣也可以用解決這個問題的算法來進行遞歸的求解。

目前已經構造處了度 d1 d 1 和 dn d n ，且度為 dn d n 的節點有 d1 d 1 個，度為 d1 d 1 的節點有 dn+1−d1 d n + 1 − d 1 個。

第三步：取一部分度為 d1 d 1 的節點，來構造子圖，這個子圖的格式同樣滿足題目中的要求，那麼取多少個度 d1 d 1 的節點合适呢？原問題中要求頂點的個數是 dn+1 d n + 1 個，在經過第一步和第二步以後，剩餘的度數變成 [d2−d1,d3−d1,...,dn−1−d1] [ d 2 − d 1 , d 3 − d 1 , . . . , d n − 1 − d 1 ] ，相當于目前最大的度是 dn−1−d1 d n − 1 − d 1 ，是以要有 dn−1−d1+1 d n − 1 − d 1 + 1 個頂點。

是以，留給度 d1 d 1 的頂點的個數等于 (dn−1−d1+1)−(dn−1−d1+1)=dn−dn−1 ( d n − 1 − d 1 + 1 ) − ( d n − 1 − d 1 + 1 ) = d n − d n − 1 ，其餘的 dn−1−d1+1 d n − 1 − d 1 + 1 個定點進行遞歸的處理，處理方式同樣遵循第1，2，3步。