Cod sursa(job #1019105)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 30 octombrie 2013 17:43:01
Problema Dame Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

int N, perm[1024];
int d1[5000], d2[5000];

bool better(int i, int j) {
    int ini = d1[i + perm[i]] + d2[N - i + perm[i]] + d1[j + perm[j]] + d2[N - j + perm[j]];
    if (ini == 4)
        return 0;
    --d1[i + perm[i]]; --d2[N - i + perm[i]];
    --d1[j + perm[j]]; --d2[N - j + perm[j]];
    ++d1[i + perm[j]]; ++d2[N - i + perm[j]];
    ++d1[j + perm[i]]; ++d2[N - j + perm[i]];
    int fin = d1[i + perm[j]] + d2[N - i + perm[j]] + d1[j + perm[i]] + d2[N - j + perm[i]];
    ++d1[i + perm[i]]; ++d2[N - i + perm[i]];
    ++d1[j + perm[j]]; ++d2[N - j + perm[j]];
    --d1[i + perm[j]]; --d2[N - i + perm[j]];
    --d1[j + perm[i]]; --d2[N - j + perm[i]];
    return ini > fin;
}

int main() {
    freopen("dame.in", "r", stdin);
    freopen("dame.out", "w", stdout);

    scanf("%d", &N);
    if (N < 3) {
        printf("1\n1 1");
        return 0;
    }
    if (N == 3) {
        printf("2\n1 1\n2 3");
        return 0;
    }
    for (int i = 1; i <= N; ++i)
        perm[i] = i;
    random_shuffle(perm + 1, perm + N + 1);

    for (int i = 1; i <= N; ++i) {
        ++d1[i + perm[i]];
        ++d2[N + i - perm[i]];
    }

    bool solution = false;
    while (!solution) {
        solution = true;
        for (int i = 1; i <= N; ++i)
            for (int j = i + 1; j <= N; ++j)
                if (better(i, j)) {
                    solution = false;
                    --d1[i + perm[i]]; --d2[N - i + perm[i]];
                    --d1[j + perm[j]]; --d2[N - j + perm[j]];
                    int tmp = perm[i];
                    perm[i] = perm[j];
                    perm[j] = tmp;
                    ++d1[i + perm[i]]; ++d2[N - i + perm[i]];
                    ++d1[j + perm[j]]; ++d2[N - j + perm[j]];
                }
    }

    printf("%d\n", N);
    for (int i = 1; i <= N; ++i)
        printf("%d %d\n", i, perm[i]);
    return 0;
}