# Cod sursa(job #542564)

Utilizator Data 26 februarie 2011 14:59:23 Sortari2 0 cpp done Romanian Master in Mathematics and Sciences 2011, Ziua 2 1.16 kb
``````#include<stdio.h>

int a[1001],k[1001],nr,aux,nr1,nrm,b[1001],nrt,n;

void back1(int x)
{
int i,j,o;

if(x!=nr+1)
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(a[i]>a[j])
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
nrm++;
for(o=1;o<5;o++)
if(a[o]>a[o+1])
o=10;

if(o!=11)
if(nr1>nrm)
nr1=nrm;

back1(x+1);

aux=a[i];
a[i]=a[j];
a[j]=aux;
nrm--;
}
}

void back(int x)
{
int i,j;

if(x==n+1)
{
nr=0;

for(i=1,nr=0;i<n;i++)
for(j=i+1;j<=n;j++)
if(a[i]>a[j])
nr++;

for(i=1;i<=n;i++)
b[i]=a[i];

for(i=1,nr=0;i<n;i++)
if(b[i]>b[i+1])
{
aux=b[i];
b[i]=b[i+1];
b[i+1]=aux;
i=0;
nr++;
}

nr1=nr+1;
nrm=0;

back1(1);

if(nr>nr1)
nrt++;

}
else
for(i=1;i<=n;i++)
if(k[i]==0)
{
k[i]=1;
a[x]=i;
back(x+1);
k[i]=0;
}
}

int main()
{
freopen("sortare2.in","r",stdin);
freopen("sortare2.out","w",stdout);

scanf("%d",&n);

back(1);

printf("%d",nrt%999017);

return 0;
}``````