Cod sursa(job #555891)

Utilizator tinkyAndrei Ilisei tinky Data 15 martie 2011 20:35:41
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
#define ll long long
using namespace std;
struct asd{ll b,c,d,x;};
ll n,s,nn;
ll a[102];
asd v[1000005];
void citire()
{
	ll i;
	ifstream in("loto.in");
	in>>n>>s;
	for (i=1;i<=n;i++)
		in>>a[i];
}

int cmp(asd c, asd b)
{
	return c.x<b.x;
}

int main()
{
	ll i,j,k,l,inc,sf,mij;
	ofstream out("loto.out");
	citire();
	l=0;
	for (i=1;i<=n;i++)
		for (j=i;j<=n;j++)
			for (k=j;k<=n;k++)
			{
				l++;
				v[l].x=a[i]+a[j]+a[k];
				v[l].b=i;
				v[l].c=j;
				v[l].d=k;				
			}	
	nn=l;
	sort(v+1,v+nn+1,cmp);
	/*for (i=1;i<=nn;i++)
		out<<v[i].x<<" ";
	out<<'\n';*/
	for (i=1;i<=nn;i++)
	{
		inc=1; sf=nn;
		while (inc<=sf)
		{
			mij=(inc+sf)/2;
			if (v[i].x+v[mij].x==s)
			{
				out<<a[v[i].b]<<" "<<a[v[i].c]<<" "<<a[v[i].d]<<" "<<a[v[mij].b]<<" "<<a[v[mij].c]<<" "<<a[v[mij].d]<<'\n';
				return 0;
			}
			if (v[mij].x+v[i].x<s)
				inc=mij+1;
			else
				sf=mij-1;
		}
	}
	out<<"-1;\n";
}