p138.ans1
======================
6
4 3
4 1
2 4
2 1
4 2
2 4

=================
p138.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    /*
     * The games form a chain where the winner of each game plays the next, so
     * game g and game g+1 share exactly one player (the carried-over winner).
     * The total number of games is G = (sum of all game counts) / 2.
     *
     * Sort players by remaining game count descending (perm records original
     * indices). Build the winner column greedily: while the busiest player
     * still owes more than one game, make him the winner of the next game and
     * defer choosing his opponent; when he owes exactly one, he plays the next
     * player and we advance. We then fill each deferred opponent slot with the
     * next player that still has games left. Outputting (winner, loser) per
     * game with the winner first satisfies the "winner plays next" rule.
     */

    int sum_deg = accumulate(a.begin(), a.end(), 0);
    assert(sum_deg % 2 == 0);

    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    sort(perm.begin(), perm.end(), [&](int i, int j) {
        return a[i] > a[j];
    });
    sort(a.rbegin(), a.rend());

    vector<pair<int, int>> matches;
    int pos = 0;
    for(int i = 0; i < sum_deg / 2; i++) {
        if(a[pos] == 1) {
            matches.emplace_back(pos + 1, pos);
            a[pos]--;
            a[pos + 1]--;
            pos++;
        } else {
            matches.emplace_back(pos, -1);
            a[pos]--;
        }
    }

    for(auto& match: matches) {
        if(match.second != -1) {
            continue;
        }
        while(a[pos] == 0) {
            pos++;
        }

        match.second = pos;
        a[pos]--;
    }

    cout << matches.size() << '\n';
    for(const auto& match: matches) {
        cout << perm[match.first] + 1 << ' ' << perm[match.second] + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p138.in1
======================
4
2 4 1 5

=================
statement.txt
======================
138. Games of Chess

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


N friends gathered in order to play chess, according to the following rules. In the first game, two of the N friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the N friends played, find a schedule for the games, so that the above rules are obeyed.


Input

The first line contains the number of friends N (2<=N<=100). The second line contains N integers, separated by blanks, representing the number of games each friend played. The first number represents the number of games played by the first friend, the second number represents the number of games played by the second friend and so on..


Output

The first line should contain the number of games played by all the friends (it will be an integer between 1 and 10 000, for every test case). Let's suppose this number is G. Then, G lines follow, each of them containing two integers, describing the games. The first line contains the numbers of the two friends who played the first game. The friend printed first is considered to be the winner. Each of the next G-1 lines contain the integers a and b, where a<>b and a or b is the winner of the previous game. The friend printed first on the line is considered to be the winner of the game.
It is guaranteed that for every test case there will be at least one possible scheduling of the games.


Sample Input

4
2 4 1 5
Sample Output

6
4 3
4 1
2 4
2 1
4 2
2 4
Author	: Mugurel Ionut Andreica
Resource	: SSU::Online Contester Fall Contest #2
Date	: Fall 2002

=================
