Pagini recente » Cod sursa (job #979799) | Cod sursa (job #1227)
Cod sursa(job #1227)
#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;
}