Cod sursa(job #331928)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 15 iulie 2009 21:14:20
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
#include <algorithm>
using namespace std;
#define N 1000000
int v[N],sum,min=100000000,nr;
struct loto {int x,y,z,s;}a[N];
short int n;
void citire()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%hd%d",&n,&sum);
	for (int i=1; i<=n; ++i)
		scanf("%d",&v[i]);
}
bool compar(const loto &d, const loto &f)
{
	return (d.s<f.s);
}
void sume()
{
	for (int i=1; i<=n; ++i)
		for (int j=i; j<=n; ++j)
			for (int k=j; k<=n; ++k)
			{
				a[++nr].x=v[i];
				a[nr].y=v[j];
				a[nr].z=v[k];
				a[nr].s=v[i]+v[j]+v[k];
			}
	sort(a+1, a+nr+1, compar);
}
int caut (int p, int x1)
{
	int u=nr,m;
	while (p!=u)
	{
		m=(p+u)/2;
		if (a[m].s>=x1)
			u=m;
		else
			p=m+1;
	}
	if (a[p].s==x1)
		return p;
	return -1;
}
void search()
{
	int ant=0;
	for (int i=1; i<=nr; ++i)
	{
		if (ant)
			while (a[i+1].s==ant&&i+1<=nr)
				++i;
		ant=sum-a[i].s;
		int c=caut (i,ant);
		if (c!=-1)
		{
			printf("%d %d %d %d %d %d",a[i].x,a[i].y,a[i].z,a[c].x,a[c].y,a[c].z);
			return;
		}			
	}
	printf("-1");
}
int main()
{
	citire();
	sume();
	search();
	return 0;
}