Cod sursa(job #447189)

Utilizator voikybodea voichita voiky Data 27 aprilie 2010 22:19:58
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>
using namespace std;

int n,s,x[101],suma[1000001],p=0;

int caut(int st,int dr,int valoare)
{
	int gas=0;
	while(st<=dr && gas==0)
	{
		int m=st+(dr-st)/2;
		if(valoare==suma[m])gas=1;
		else if(valoare>suma[m])st=m+1;
			 else dr=m-1;
	}
	return gas;
}

int main()
{
	ifstream f("loto.in");ofstream g("loto.out");
	int i,j,k,s2;
	f>>n>>s;for(i=1;i<=n;i++)f>>x[i];
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)suma[++p]=x[i]+x[j]+x[k];				
	sort(suma,suma+p);
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				s2=s-x[i]-x[j]-x[k];
				if(caut(1,p,s2))
				{
					g<<x[i]<<' '<<x[j]<<' '<<x[k]<<' ';
					for(i=1;i<=n;i++)
						for(j=i;j<=n;j++)
							for(k=j;k<=n;k++)					
								if(s2==x[i]+x[j]+x[k])
							    {
									g<<x[i]<<' '<<x[j]<<' '<<x[k];
									f.close();g.close();
									return 0;
								}	
				}			
			}	
	g<<-1;
	f.close();g.close();
	return 0;
}