Cod sursa(job #1698823)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 5 mai 2016 14:53:14
Problema Dame Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
/*
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;
    if (n == 2){
        fout<<1<<"\n"<<1<<" "<<1;
        return 0;
    }
    if (n == 3){
        fout<<2<<"\n"<<1<<" "<<1<<"\n"<<2<<" "<<3;
        return 0;
    }
    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;
    }

    //if (n%12 == 0 || n%12 == 1 || n%12 == 4 || n%12 == 5 || n%12==6 || n%12 == 7 || n%12 == 11){

    //}

    fout<<n<<"\n";
    for (i=1;i<=k;i++){
        fout<<i<<" "<<v[i]<<"\n";
    }


    return 0;
}