Cod sursa(job #555864)

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

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

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