Cod sursa(job #878259)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 14 februarie 2013 11:33:20
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <algorithm>

using namespace std;

int sume[1000005];

int main()
{
	ifstream fin("loto.in");
	ofstream fout("loto.out");
	
	int n,s,i,j,k,v[101];
	
	fin>>n;
	fin>>s;
	
	for(i=0;i<n;i++)
		fin>>v[i];
	
	int poz=0;
	
	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			for(k=j;k<n;k++)
				sume[poz++]=v[i]+v[j]+v[k];
			
	//cout<<"gata 1"<<endl;
	sort(sume,sume+poz);
	
	//cout<<"gata 2"<<endl;
	
	int cautat;
	
	int cap,coada,mijl;
	
	bool gasit=false;
	
	int x1,x2,x3,x4,x5,x6;
	
	for(i=0;i<n && !gasit;i++)
		for(j=i;j<n && !gasit;j++)
			for(k=j;k<n && !gasit;k++)
			{
				//cout<<"i="<<i<<" j="<<j<<" k="<<k<<endl;
				cautat=s-(v[i]+v[j]+v[k]);
				
				if(cautat<=0)
				{
					i=n;
					j=n;
					k=n;
					break;
				}
				
				cap=0;
				coada=poz-1;
				mijl=(poz-1)/2;
				
				
				while(cap<=coada)
				{
					if(sume[mijl]==cautat)
					{
						gasit=true;
						x1=v[i];
						x2=v[j];
						x3=v[k];
						break;
					}
					else if(sume[mijl]<cautat)
					{	
						cap=mijl+1;
					}
					else
					{
						coada=mijl-1;
					}
					
					mijl=(cap+coada)/2;
				}
				
			}
	
	if(!gasit)
	{
		fout<<"-1\n";
	}
	else
	{
		fout<<x1<<' '<<x2<<' '<<x3<<' ';
		
		cautat=s-(x1+x2+x3);
		
		gasit=false;
	for(i=0;i<n && !gasit;i++)
		for(j=i;j<n && !gasit;j++)
			for(k=j;k<n && !gasit;k++)
			{
				if((v[i]+v[j]+v[k])==cautat)
				{
					x4=v[i];
					x5=v[j];
					x6=v[k];
					gasit=true;
					break;
				}
			}
			
		fout<<x4<<' '<<x5<<' '<<x6<<'\n';
	}
	
	fin.close();
	fout.close();
	
	return 0;
}