Cod sursa(job #447183)

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

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

void inter(int st,int m,int dr)
{
	int i=st,j=m+1,k=st-1;
	while(i<=m && j<=dr)
		if(suma[i]<suma[j])y[++k]=suma[i++];
		else y[++k]=suma[j++];
	while(i<=m)y[++k]=suma[i++];
	while(j<=dr)y[++k]=suma[j++];
	for(i=st;i<=dr;i++)suma[i]=y[i];
}

void ordon(int st,int dr)
{
	if(st<dr)
	{
		int m=st+(dr-st)/2;
		ordon(st,m);ordon(m+1,dr);
		inter(st,m,dr);
	}
}

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];				
	ordon(1,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;
}