Cod sursa(job #757739)

Utilizator GrimpowRadu Andrei Grimpow Data 13 iunie 2012 12:18:24
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define f first
#define s second
#define mp make_pair
using namespace std;

int v[105];
vector< pair<int, pair<int, int> >  > vct;
int cautbin(int x)
{
	int ls=0,ld=vct.size(),mij;
	while(ls<=ld)
	{
		mij=(ls+ld)/2;
		if(vct[mij].f==x)
			return mij;
		if(vct[mij].f<x)
			ls=mij+1;
		if(vct[mij].f>x)
			ld=mij-1;
	}
	return -1;
}

int main()
{
	int n,Sum;
	freopen("loto.in","r", stdin);
	freopen("loto.out","w", stdout);
	scanf("%d %d",&n,&Sum);
	for(int i=1;i<=n;i++)
		scanf("%d",&v[i]);
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			for(int k=j;k<=n;k++)
				if(v[i]+v[j]+v[k]<=Sum)
					vct.push_back(mp(v[i]+v[j]+v[k],mp(v[j],v[k])));
				
	sort(vct.begin(),vct.end());
	for(unsigned int i=0;i<vct.size();i++)
	{
		int poz=cautbin(Sum-vct[i].f);
		if(poz!=-1)
		{
			printf("%d %d %d %d %d %d",vct[i].f-vct[i].s.f-vct[i].s.s,
				vct[i].s.f,vct[i].s.s,vct[poz].f-vct[poz].s.f-vct[poz].s.s,vct[poz].s.f,vct[poz].s.s);
			return 0;
	    }
	}
	printf("-1");

	return 0;
}