Cod sursa(job #331292)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 13 iulie 2009 15:59:14
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

struct suma{
	int x1;
	int x2;
	int x3;
	int S;
};

struct suma v[1000000];
int nr=0;

bool cmp(const suma &a1, const suma &a2)
{
	return a1.S <a2.S;
}

int search(int x)
{
	int mij,st,dr,gasit=-1;

	st=0;
	dr=nr;
	
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if(v[mij].S==x)
		{
			gasit=mij;
			break;
		}
		if(x>v[mij].S)
			st=mij+1;
		else
			dr=mij-1;
	}
	return gasit;
}

int main()
{
	int n,x[100],s,i,j,k,found=0,s1,poz;
	

	FILE *f=fopen("loto.in","r");
	fscanf(f,"%i%i",&n,&s);
	for(i=0;i<n;i++)
		fscanf(f,"%i",x+i);
	fclose(f);
	f=fopen("loto.out","w");

	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			for(k=j;k<n;k++)
			{
				v[nr].x1=i;
				v[nr].x2=j;
				v[nr].x3=k;
				v[nr].S=x[i]+x[j]+x[k];
				nr++;
			}
	sort(v,v+nr,cmp);

	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			for(k=j;k<n;k++)
			{
				s1=s;
				if(x[i]+x[j]+x[k]<=s1)
					s1-=x[i]+x[j]+x[k];
				poz=search(s1);
				if(poz!=-1)
				{
					found=1;
					fprintf(f,"%i %i %i %i %i %i\n",x[i],x[j],x[k],x[v[poz].x1],x[v[poz].x2],x[v[poz].x3]);
					break;
				}
			}
	if(found==0)
		fprintf(f,"%s\n","-1");
	return 0;	
}