Pagini recente » Cod sursa (job #79618) | Cod sursa (job #3268386) | Cod sursa (job #2231676) | Cod sursa (job #740336) | Cod sursa (job #1698817)
/*
O alta solutie , matematica, se bazeaza pe un sablon de construire a solutiei in functie de restul lui N la 12.
Se insereaza numerele pare de la 2 la N intr-o lista
Daca restul lui N la 12 este 3 sau 9 se muta 2 la sfarsitul listei
Se insereaza numerele impare de la 1 la N in lista
Daca restul este 8 se interschimba perechile (3 1, 7 5, ...)
Daca restul este 2 se interschimba 1 cu 3 si 5 se muta la sfarsitul listei
Daca restul este 3 sau 9 se muta 1 si 3 la sfarsitul listei
Lista va codifica o solutie cum s-a precizat si inainte, al i-lea element reprezetand o dama pe randul i si pe coloana listai.
Aceasta solutie O(N) este preluata de aici
*/
#include <fstream>
using namespace std;
int n,i,v[1001],x,aux,k;
ifstream fin ("dame.in");
ofstream fout ("dame.out");
int main (){
fin>>n;
k = 0;
for (i=2;i<=n;i+=2)
v[++k] = i;
if (n % 12 == 3 || n % 12 == 9){
for (i=1;i<k;i++)
v[i] = v[i+1];
v[k] = 2;
}
x = k;
for (i=1;i<=n;i+=2)
v[++k] = i;
if (n%12 == 8){
for (i=x+1;i<=k;i+=2){
aux = v[i];
v[i] = v[i+1];
v[i+1] = aux;
}
}
if (n % 12 == 2){
aux = v[x+1];
v[x+1] = v[x+2];
v[x+2] = aux;
for (i=x+3;i<=k;i++)
v[i] = v[i+1];
v[k] = 5;
}
if (n % 12 == 3 || n % 12 == 9){
for (i=x+1;i<=k;i+=2){
v[i] = v[i+2];
v[i+1] = v[i+3];
}
v[k-1] = 1;
v[k] = 3;
}
fout<<k<<"\n";
for (i=1;i<=k;i++){
fout<<i<<" "<<v[i]<<"\n";
}
return 0;
}