Cod sursa(job #541942)

Utilizator zeroblitz36FMI - Roscaneanu George zeroblitz36 Data 25 februarie 2011 16:39:34
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<cstdio>
FILE *in,*out;
int v[100],man,s,flag,i,j,k,l,m,o,n,max;
void quick(int v[],int left,int right)
{
	int i=left,j=right,p=v[(left+right)/2],man;
	while(i<=j)
	{
		while(v[i]>p)i++;
		while(v[j]<p)j--;
		if(i<=j){man=v[i];v[i]=v[j];v[j]=man;i++;j--;}
	}
	if(left<j)quick(v,left,j);
	if(i<right)quick(v,i,right);
}
int main()
{
	//Citesc informatia din fisier, sirul de numere este memorat in vectorul v
	in=fopen("loto.in","r");
	fscanf(in,"%d %d",&n,&s);
	for(i=0;i<n;i++)
		fscanf(in,"%d",&v[i]);
	fclose(in);
	//Sortez descrescator folosind functia QuickSort
	quick(v,0,n-1);
	out=fopen("loto.out","w");
	flag=1;
	//Daca te uiti bine vei vedea ca daca se va gasi raspuns, va fi un sir descrescator
	for(i=0;flag&&i<n&&v[i]*6>=s;i++)//Daca cel mai mare numar din sir*6 nu poate depasi s, atunci nu merita sa cautam numere mai mici pentru primul numar
	for(j=i;flag&&j<n&&v[i]+v[j]*5>=s&&v[i]+v[n-1]*5<=s;j++)//Restul for-urilor au aproape aceasi idee doar ca mai adaug ceva.
	for(k=j;flag&&k<n&&v[i]+v[j]+v[k]*4>=s&&v[i]+v[j]+v[n-1]*4<=s;k++)//Daca cel mai mic numar posibil ar ocupa restul spatiilor din sir, 
	for(l=k;flag&&l<n&&v[i]+v[j]+v[k]+v[l]*3>=s&&v[i]+v[j]+v[k]+v[n-1]*3<=s;l++)//si suma sirului ar fi mai mare decat s,inseamna ca nu mai merita
	for(m=l;flag&&m<n&&v[i]+v[j]+v[k]+v[l]+v[m]*2>=s&&v[i]+v[j]+v[k]+v[l]+v[n-1]*2<=s;m++)//sa cautam numere mai mici
	for(o=m;flag&&o<n&&v[i]+v[j]+v[k]+v[l]+v[m]+v[o]>=s;o++)
	if(v[i]+v[j]+v[k]+v[l]+v[m]+v[o]==s){fprintf(out,"%d %d %d %d %d %d",v[i],v[j],v[k],v[l],v[m],v[o]);flag=0;}
	//Daca se gaseste sirul dorit, flag=0, aceste semnaland la restul for-urilor sa nu mai caute alta solutie.
	//Daca flag ramane neschimbat,flag==1.Atunci inseamna ca nu sa gasit, deci afisam -1
	if(flag)fprintf(out,"-1");
	fclose(out);
	return 0;
}