Pagini recente » Cod sursa (job #2378785) | Cod sursa (job #1309419) | Cod sursa (job #1631174) | Cod sursa (job #237819) | Cod sursa (job #1019105)
#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;
}