Cod sursa(job #1228)

Utilizator astronomyAirinei Adrian astronomy Data 12 decembrie 2006 22:01:31
Problema Dame Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 1024

int N, A[MAXN], used[MAXN], d1[2*MAXN], d2[2*MAXN];

void solve(void)
{
    int i, j, t, k, d, ok, ok2;

    srand(time(0));
    
    while(1)
    {
        memset(used, 0, sizeof(used)), memset(d1, 0, sizeof(d1)), memset(d2, 0, sizeof(d2));
        for(i = 1; i <= N; i++)
        {
            j = rand() % N + 1;
            while(used[j])
                j = rand() % N + 1;
            used[j] = 1, A[i] = j, d1[i+j-1]++, d2[N-i+j]++;
        }
        for(i = 1; i <= N; i++)
         for(j = i+1; j <= N; j++)
         {
            t = A[i], k = A[j];
            d = (-1)*(d1[i+t-1] > 1) + (-1)*(d2[N-i+t] > 1) + (-1)*(d1[j+k-1] > 1) + (-1)*(d2[N-j+k] > 1);
            d += (d1[j+t-1] > 0) + (d2[N-j+t] > 0) + (d1[i-k+1] > 0) + (d2[N-i+k] > 0);
            if(d < 0)
            {
                ok = 1, A[i] = k, A[j] = t;
                if(d1[i+t-1]) d1[i+t-1]--;
                if(d2[N-i+t]) d2[N-i+t]--;
                if(d1[j+k-1]) d1[j+k-1]--;
                if(d2[N-j+k]) d2[N-j+k]--;
                d1[j+t-1]++, d2[N-j+t]++, d1[i+k-1]++, d2[N-i+k]++;
            }
         }
        for(i = 1; i <= 2*N-1; i++)
         if(d1[i] > 1 || d2[i] > 1)
         {
            t++; break ;
         }
        if(i == 2*N) break ;
    }
}

int main(void)
{
    freopen("dame.in", "rt", stdin);
    freopen("dame.out", "wt", stdout);

    int i;
    scanf("%d\n", &N);

    if(N <= 2)
    {
        printf("1\n1 1\n"); return 0;
    }
    if(N == 3)
    {
        printf("2\n1 1\n3 2\n"); return 0;
    }
    
    solve();

    for(printf("%d\n", N), i = 1; i <= N; i++)
        printf("%d %d\n", i, A[i]);

    return 0;
}