Cod sursa(job #52411)

Utilizator moga_florianFlorian MOGA moga_florian Data 18 aprilie 2007 20:30:18
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
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;
}