Cod sursa(job #470574)

Utilizator Catah15Catalin Haidau Catah15 Data 14 iulie 2010 17:25:15
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
# include <fstream>
# define maxx 101
# define maxs 600000
using namespace std;

ifstream f("loto.in");
ofstream g("loto.out");

int n,s,x[maxx],sum[maxs],m;

void citire()
{
	int i;
	f>>n>>s;
	for(i=1; i<=n; i++)
		f>>x[i];
	f.close();
}

void sume_partiale()
{
	int i,j,t;
	for(i=1; i<=n; i++)
		for(j=i; j<=n; j++)
			for(t=j; t<=n; t++)
				sum[++m]=x[i]+x[j]+x[t];
				
}	

int search(int z, int i, int j)
{
	int mid;
	while(i<=j)
	{
		mid=(i+j)/2;
		if(z==sum[mid]) return 1;
			else 
				if(z>sum[mid]) i=mid+1;
					else j=mid-1;
	}
	return 0;
}


void first_3(int z)
{
	int i,j,t;
	for(i=1; i<=n; i++)
		for(j=i; j<=n; j++)
			for(t=j; t<=n; t++)
				if(x[i]+x[j]+x[t]==z)
					g<<x[i]<<" "<<x[j]<<" "<<x[t];
					
}

int last_3()
{
	int i,j,t,aux;
	for(i=1; i<=n; i++)
		for(j=i; j<=n; j++)
			for(t=j; t<=n; t++)
				if( search(s-x[i]-x[j]-x[t],1,m) )
				{
					g<<x[i]<<" "<<x[j]<<" "<<x[t]<<" ";
					aux=s-x[i]-x[j]-x[t];
					first_3(aux);
					return 1;
				}
	return 0;
}
	

	
int main()
{
	citire();
	sume_partiale();
	
	if ( !last_3 () ) g<<-1;
	
	g.close ();
	return 0;
}