Cod sursa(job #642216)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 30 noiembrie 2011 18:30:15
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

const int N=101;

struct sum{
	int a,b,c,val;
}s[N*N*N];

int v[N],n,size,suma,pasf;

void citire(){
	int i;
	in>>n>>suma;
	for(i=1;i<=n;++i)
		in>>v[i];
}

inline bool comp(sum a,sum b){
	if(a.val<b.val)
		return true;
	return false;
}

bool caut(int b){
	int x=s[b].val;
	int i=0,pas;
	pas=pasf;
	for(i=0;pas;pas>>=1){
		if(s[i+pas].val<=(suma-x) && i+pas<=size){
			i+=pas;
			continue;
		}
	}
	if(s[i].val==suma-x){
		out<<s[b].a<<" "<<s[b].b<<" "<<s[b].c<<" "<<s[i].a<<" "<<s[i].b<<" "<<s[i].c;
		return true;
	}
	return false;
}
	

void rezolvare(){
	int i,j,k;
	for(i=1;i<=n;++i){
		for(j=i;j<=n;++j){
			for(k=j;k<=n;++k){
				if(v[i]+v[j]+v[k]<suma){
					size++;
					s[size].val=v[i]+v[j]+v[k];
					s[size].a=i;
					s[size].b=j;
					s[size].c=k;
				}
			}
		}
	}
	sort(s+1,s+size+1,comp);
	for(pasf=1;pasf<=size;pasf<<=1);
	for(i=1;i<=size;++i){
		if(caut(i))
			return;
	}
	out<<"-1";
}

int main(){
	citire();
	rezolvare();
	return 0;
}