2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest A. Toda 2 贪心 + 暴力

A group of n friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the i-th friend is ri.

The friends decided to take part in the championship as a team. But they should have equal ratings to be allowed to compose a single team consisting of all n friends. So the friends are faced with the problem: how to make all their ratings equal.

One way to change ratings is to willingly lose in some matches. Friends can form a party consisting of two to five(but not more than n) friends and play a match in the game. When the party loses, the rating of each of its members decreases by 1. A rating can't become negative, so ri = 0 doesn't change after losing.

The friends can take part in multiple matches, each time making a party from any subset of friends (but remember about constraints on party size: from 2 to 5 members).

The friends want to make their ratings equal but as high as possible.

Help the friends develop a strategy of losing the matches so that all their ratings become equal and the resulting rating is maximum possible.

Input

The first line contains a single integer n (2 ≤ n ≤ 100) — the number of friends.

The second line contains n non-negative integers r1, r2, ..., rn (0 ≤ ri ≤ 100), where ri is the initial rating of the i-th friend.

Output

In the first line, print a single integer R — the final rating of each of the friends.

In the second line, print integer t — the number of matches the friends have to play. Each of the following t lines should contain n characters '0' or '1', where the j-th character of the i-th line is equal to:

'0', if friend j should not play in match i,
'1', if friend j should play in match i.

Each line should contain between two and five characters '1', inclusive.

The value t should not exceed 104, it is guaranteed that such solution exists.

Remember that you shouldn't minimize the value t, but you should maximize R. If there are multiple solutions, print any of them.

Examples

input

5
4 5 1 7 4

output

input

2
1 2

output

input

3
1 1 1

output

1
0

http://codeforces.com/contest/730/problem/0

题目给定n个数字，要求他们相等，并且每次只能选取【2, 5】个人出来减去1，问最后剩下的最大数字和方案是什么。

首先这题我没有用二分答案，因为注意到。

1、剩下的数字是相同的，因此每次选出最小的数字作为基准。

2、如果所有数字相同，则可以跳出循环了。

3、如果大于最小数字的个数是[2,5]个之间，而且，他们都是比最小数字大1的话，则可以使这些数字全部减去1.

因为如果除了最小数字，剩下的数字中全部都是mi + 1的话，你的决策不会影响到后面。因为大家的数字都相同嘛。如果不同，那就不行了。可能会导致（就是样例1，模拟一下就好）后面的每次只有1个数字要减，这不在【2， 5】的范围。

4、除了上面那些外，我们用贪心，每次只选出最大的两个数字去减1。选取两个，是因为他至少要两个，而且这样选，不会让本来就小的数字被减了，后面的每次只有1个数字要减

还有就是，方案是必定存在的而且在1e4之内

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 100 + 20;
int ans[maxn * maxn][maxn];
void work() {
    int n;
    cin >> n;
    int r[maxn];
    for (int i = 1; i <= n; ++i) cin >> r[i];
//    cout << "ff" << endl;
    int toans = 0;
    while (true) {
        int cnt = 0;
        int flagCnt = 0;
        int mi = inf;
        for (int i = 1; i <= n; ++i) mi = min(mi, r[i]);
        for (int i = 1; i <= n; ++i) {
            if (r[i] - mi >= 2) flagCnt = 1;
            if (r[i] != mi) cnt++;
        }
        if (cnt == 0) break;
        ++toans;
//        cout << cnt << endl;
        if (cnt >= 2 && cnt <= 5 && !flagCnt) {
            for (int i = 1; i <= n; ++i) {
                if (r[i] != mi) {
                    ans[toans][i] = 1;
                    r[i]--;
                }
            }
        } else {
            int mx1 = -inf, posmx1 = -inf, mx2 = -inf, posmx2 = -inf;
            for (int i = 1; i <= n; ++i) {
                if (mx1 < r[i]) {
                    mx2 = mx1; posmx2 = posmx1;
                    mx1 = r[i]; posmx1 = i;
                } else if (mx2 < r[i]) {
                    mx2 = r[i];
                    posmx2 = i;
                }
            }
//            cout << posmx1 << " " << posmx2 << endl;
            ans[toans][posmx1] = 1;
            ans[toans][posmx2] = 1;
            r[posmx1] = max(0, r[posmx1] - 1);
            r[posmx2] = max(0, r[posmx2] - 1);
        }
//        cout << "ff" << endl;
    }
    printf("%d
", r[1]);
    printf("%d
", toans);
    for (int i = 1; i <= toans; ++i) {
        for (int j = 1; j <= n; ++j) {
            printf("%d", ans[i][j]);
        }
        printf("
");
    }
}

int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    work();
    return 0;
}

View Code