Cod sursa(job #695799)

Utilizator cipry13Hotea Ciprian cipry13 Data 28 februarie 2012 14:51:51
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream>
#include<algorithm>
using namespace std;
int a[1000001],v[101],l,b[10];
int cautarebinara(int x)
{
	int p,q,mij;
	p=1;
	q=l;
	while(p<=q) {
		mij=(p+q)/2;
		if(a[mij]>x)
			q=mij-1;
		else if(a[mij]<x)
			p=mij+1;
		else
			return 1;
	}
	return 0;
}
int main ()
{
	int n,i,j,k,sum,d,s,c;
	ifstream f("loto.in");
	ofstream g("loto.out");
	f>>n>>sum;
	for(i=1;i<=n;i++)
		f>>v[i];
	f.close();
	l=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				if((v[i]+v[j]+v[k])<=sum) {
					l++;
					a[l]=v[i]+v[j]+v[k];
				}
	sort(a+1,a+l+1);
	d=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++) {
				s=v[i]+v[j]+v[k];
				if(cautarebinara(sum-s)==1) {
					b[1]=v[i];
					b[2]=v[j];
					b[3]=v[k];
					c=s;
					i=n+1;
					j=n+1;
					k=n+1;
					d=1;
					break;
				}
			}
	if(d==0)
		g<<"-1";
	else {
		sum=sum-c;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				for(k=1;k<=n;k++) {
					s=v[i]+v[j]+v[k];
					if(s==sum) {
						b[4]=v[i];
						b[5]=v[j];
						b[6]=v[k];
						i=n+1;
						j=n+1;
						k=n+1;
						break;
					}
				}
		for(i=1;i<=6;i++)
			g<<b[i]<<" ";
	}
	g.close();
	return 0;
}