Cod sursa(job #121762)

Utilizator hadesgamesTache Alexandru hadesgames Data 9 ianuarie 2008 17:32:53
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct ceva{
	int c,a,nr;
};
ceva d[700];
int a[700],c[700];
/*int compare2( const void* a, const void* b ) {
   ceva* arg1 = (ceva*) a;
   ceva* arg2 = (ceva*) b;
   if( arg1->c < arg2->c ) return -1;
   else if( arg1->c == arg2->c ) return 0;
   else return 1;
 }*/   
int compare2(const void *a,const void *b)
{
	ceva *aa,*bb;
	aa=(ceva *)a;
	bb=(ceva *)b;
	if (aa->c<bb->c)
		return -1;
	if (aa->c==bb->c)
		return 0;
	return 1; 
}
int main()
{
	FILE *in,*out;
	int min,timp,i,j,k,n,cul,e,t=-1,aux;
	in=fopen("barman.in","r");
	out=fopen("barman.out","w");
	fscanf(in,"%d",&n);
	for (i=0;i<n;i++)
	{
		fscanf(in,"%d",&a[i]);
		e=1;
		for (j=0;j<=t;j++)
		{
			if (d[j].c==a[i])
			{
				d[j].nr++;
				e=0;
			}
		}
		if (e)
		{
			t++;
			d[t].c=a[i];
			d[t].nr=1;
		}
	}
	qsort(d,t+1,sizeof(d[0]),compare2);
	for (k=0;k<n;k++)
	{
		timp=0;
		for (i=0;i<n;i++)
		{
			c[i]=a[i];
		}
		for (i=0;i<t;i++)
			d[i].a=0;
		cul=0;
		for (i=k;i<n;i++)
		if (c[i]==d[cul].c)
		{
			d[cul].a++;
			if (d[cul].a==d[cul].nr)
				cul++;
		}
		else
		{
			for (j=0;j<n;j++)
			{
				if(c[j]==d[cul].c )
				if (j<k || j>i)
				{
					aux=c[i];
					c[i]=c[j];
					c[j]=aux;
					timp+=40+2*abs(i-j);
					d[cul].a++;
					if (d[cul].a==d[cul].nr)
						cul++;
					break;
				}
			}
		}
		for (i=0;i<k;i++)
		if (c[i]==d[cul].c)
		{
			d[cul].a++;
			if (d[cul].a==d[cul].nr)
				cul++;
		}
		else
		{
			for (j=0;j<n;j++)
			{
				if(c[j]==d[cul].c )
				if (j<k && j>i)
				{
					aux=c[i];
					c[i]=c[j];
					c[j]=aux;
					timp+=40+2*abs(i-j);
					d[cul].a++;
					if (d[cul].a==d[cul].nr)
						cul++;
					break;
				}
			}
		}
		if (timp<min||k==0)
			min=timp;
	}
	fprintf(out,"%d\n",min);
	fclose(in);
	fclose(out);
	return 0;
}