Pagini recente » Cod sursa (job #18666) | Cod sursa (job #102181) | Cod sursa (job #2355556) | Cod sursa (job #2627422) | Cod sursa (job #52411)
Cod sursa(job #52411)
using namespace std;
#include<fstream>
#include<stdio.h>
#define Nmax 605
int a[Nmax],val[Nmax];
int nra[Nmax],nrval[Nmax];
void intersc(int i,int j)
{
int aux;
aux=val[i];
val[i]=val[j];
val[j]=aux;
}
int main()
{
FILE *fin=fopen("barman.in","r"),
*fout=fopen("barman.out","w");
int N,i,j,k;
fscanf(fin,"%d",&N);
for(i=1;i<=N;i++)
fscanf(fin,"%d",&a[i]);
for(i=1;i<=N;i++)
{
val[i]=a[i];
j=i;
while(j/2 && val[j/2]<val[j])
{
intersc(j/2,j);
j/=2;
}
}
i=N;
while(i)
{
intersc(1,i);
i--;
j=1;
while(1)
{
k=2*j;
if(k>i) break;
if(k+1<=i && val[k+1]>val[k]) k++;
if(val[j] >= val[k]) break;
intersc(j,k);
j=k;
}
}
int sol=1000000000,crt,q;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
val[j]=val[j+1];
val[N]=val[0];
memset(nra,0,sizeof nra);
memset(nrval,0,sizeof nrval);
k=0;
for(j=1;j<=N;j++)
if(a[j] != val[j])
{
k++;
q=j-1;
while(q && !(a[q]==a[j] && nra[q]) ) q--;
if(q)
nra[j]=nra[q]+1;
else
nra[j]=1;
q=j-1;
while(q && !(val[q]==val[j] && nrval[q]) ) q--;
if(q)
nrval[j]=nrval[q]+1;
else
nrval[j]=1;
}
crt=20*k;
for(j=1;j<=N;j++)
if(a[j] != val[j])
{
k=1;
while( !(a[j]==val[k] && nra[j]==nrval[k]) ) k++;
if(j-k>0)
crt+=j-k;
else
crt-=j-k;
}
if(crt<sol)
sol=crt;
}
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;
}