Cod sursa(job #955065)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 30 mai 2013 20:30:08
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<fstream>
#include<algorithm>
using namespace std;

struct st
{
	int s,x,y,z;
};

st v[1000001];
int a[101],i,n,j,k,s,m,p,u,t,w;
bool e[300000001];

bool cmp(st a,st b)
{
	return a.s<b.s;
}

int main()
{
	ifstream f("loto.in");
	ofstream g("loto.out");
	f >> n >> s;
	for (i=1;i<=n;i++)
		f >> a[i];
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++)
				if (e[a[i]+a[j]+a[k]]==0)
				{
					t++;
					v[t].s=a[i]+a[j]+a[k];
					e[v[t].s]=1;
					v[t].x=a[i];
					v[t].y=a[j];
					v[t].z=a[k];
				}
	sort(v+1,v+t+1,cmp);
	for (i=1;i<=t;i++)
	{
		p=1;u=t;w=s-v[i].s;
		while (p<=u)
		{
			m=(p+u)/2;
			if (v[m].s<w)
				p=m+1;
			else if (v[m].s>w)
				u=m-1;
			else 
			{
				g << v[i].x << ' ' << v[i].y << ' ' << v[i].z << ' ' << v[m].x << ' ' << v[m].y << ' ' << v[m].z;
				return 0;
			}
		}
	}
	g << -1;
	return 0;
}