Cod sursa(job #720105)

Utilizator George25Raduta George Cristian George25 Data 22 martie 2012 12:59:20
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

typedef struct{
	int x,y,z,q;
}loto;

loto s[1002332];
int a[1011],b[100],m,i,ii,j,k,S,max1,n,st,mij,dr,poz,tt;
bool ok;
double t;

bool cmp(loto a,loto b){
	return(a.x<b.x);
}

int main(){
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d %d",&n,&S);
	for (i=1; i<=n; ++i){
		scanf("%d",&a[i]);
		if (a[i]>max1) max1=a[i];
	}
	ok=true;
	t=double (1.0*S/6);
	if (t>max1){
		ok=false;
		printf("-1");
	}
	if (ok==true){
		for (i=1; i<=n; ++i){
			for (j=i; j<=n; ++j){
				for (k=j; k<=n; ++k){
					m++;
					s[m].x=a[i]+a[j]+a[k];
					s[m].y=a[i];
					s[m].z=a[j];
					s[m].q=a[k];
				}
			}
		}
	sort(s,s+m,cmp);
	for (i=m; i>=1; --i){
		tt=S-s[i].x;
		poz=i;
		st=1;
		dr=m;
		mij=(st+dr)/2;
		ok=false;
		while (ok==false && st<=dr){
			if (s[mij].x==tt){
				ok=true;
				b[1]=s[poz].y;
				b[2]=s[poz].z;
				b[3]=s[poz].q;
				b[4]=s[mij].y;
				b[5]=s[mij].z;
				b[6]=s[mij].q;
				sort(b+1,b+7);
				for (ii=1; ii<=6; ++ii) printf("%d ",b[ii]);
				printf("\n");
			}
			else if (s[mij].x>tt){
				dr=mij-1;
				mij=(st+dr)/2;
			}
			else if (s[mij].x<tt){
				st=mij+1;
				mij=(st+dr)/2;
			}
		}
		if (ok==true) break;
	}
	if (ok==false) printf("-1\n");
	}
	return(0);
}