Cod sursa(job #418568)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 16 martie 2010 08:07:22
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,s,a[110], v[10001],m;

void desc(int ss,int &x, int &y){
	for(int i=1;i<=n;++i)
	{
		int xx=ss-a[i];
		int st=1, dr=n;
		while(st<dr){
			int m=(st+dr)/2;
			if(a[m]==xx){
				x=a[i], y=a[m];
				//cout<<ss<<"="<<x<<"+"<<y<<endl;
				return;
			}
			if(a[m]<xx)
				st=m+1;
			else
				dr=m-1;
		}
	}
}

int main ()
{
	ofstream fout("loto.out");
	ifstream f("loto.in");
	f>>n>>s;
	for (int i=1;i<=n;++i)
		f>>a[i];
		sort(a+1,a+n+1);
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
		{
			v[++m]=a[i]+a[j];
		}
	sort(v+1,v+n+1);
	int gasit=0, s1,s2,s3;
	for (int i=1;i<=m && !gasit;i++)
		for (int j=i;j<=m && !gasit;j++)
		{
			int x=s-v[i]-v[j];
			int st=j, dr=m;
			gasit=0;
			while(st<dr && !gasit){
				int mij=(st+dr)/2;
				if(v[mij]==x)
					gasit=mij;
				else
					if(v[mij]<x)
							st=mij+1;
					else
						dr=mij-1;
			}
			if(gasit)
				s1=v[i], s2=v[j],s3=v[gasit] /*, cout<<s1<<" "<<s2<<" "<<s3<<endl<<endl*/;
			
		}
	if(!gasit)
		fout<<"-1\n";
	else{
		int q1=0,q2=0,q3=0,q4=0,q5=0,q6=0;
		desc(s1,q1,q2);
		desc(s2,q3,q4);
		desc(s3,q5,q6);
//		cout<<s1<<" "<<s2<<" "<<s3<<endl;
		fout<<q1<<" "<<q2<<" "<<q3<<" "<<q4<<" "<<q5<<" "<<q6<<endl;
	}
	return 0;
}