Cod sursa(job #31454)

Utilizator pocaituDavid si Goliat pocaitu Data 16 martie 2007 01:17:08
Problema Barman Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<fstream.h>
#include<stdio.h>
#define nmax 703
#define infi 2110000000
long long n,s[nmax],s1[nmax];
inline long long minim(long long a,long long b) {return a<b?a:b;}

long long rezolva(long long x)
{long long i,j,k1,min,v[nmax],p[nmax],cost=0,viz[nmax];
 memset(p,0,sizeof(p));
 memset(viz,0,sizeof(viz));

 for(i=x;i<=n;i++)
   v[i-x+1]=s1[i];
 j=i-x+1;
 for(i=1;i<x;i++,j++)
   v[j]=s1[i];

 for(i=1;i<=n;i++)
  if(v[i]==s[i])
	{p[i]=1;viz[i]=1;}
 for(i=1;i<=n;i++)
   if(!viz[i])
	 {for(j=i-1,min=infi;j>0;j--)
		if(v[j]==s[i]&&!p[j])
		  {min=i-j+20;
		   k1=j;
		   }
	  if(min==infi)
	  for(j=i+1;j<=n;j++)
		 if(v[j]==s[i]&&!p[j])
		  {if(j-i+20<min)
			{min=j-i+20;
			k1=j;}
		   break;
		   }
	  p[k1]=1;viz[i]=1;cost+=min;
	  }
 return cost;
 }
void ordoneaza()
{long long i,j,aux;
 memcpy(s1,s,sizeof(s));
 for(i=1;i<=n;i++)
   for(j=i+1;j<=n;j++)
	 if(s1[i]>s1[j])
	  {aux=s1[i];
	   s1[i]=s1[j];
	   s1[j]=aux;
	   }
 }







int main()
{long long i,min;
 freopen("barman.in","r",stdin);
 scanf("%lld",&n);
 for(i=1;i<=n;i++)
   scanf("%lld",&s[i]);
 ordoneaza();
 for(i=1,min=infi;i<=n;i++)
  min=minim(min,rezolva(i));
 freopen("barman.out","w",stdout);
 printf("%lld",min);
 fclose(stdout);
 return 0;
 }