Cod sursa(job #750948)

Utilizator svladScurtu Vlad svlad Data 23 mai 2012 18:19:25
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>
using namespace std;
long v[1000];
typedef struct {int x,y,z,s;} PUNCT;
PUNCT w[20000];
int cmp(PUNCT a, PUNCT b)
{
	return(a.s<b.s);
}
int main()
{
	ifstream f("loto.in");
	ofstream g("loto.out");
	int n,i,j,OK=0,x,k,q,t,m;
	long long S;
	f>>n; f>>S; k=0;
	for(i=1;i<=n;i++) 
	{	f>>v[i];}
	for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		 { for(q=1;q<=n;q++)
			 { w[++k].s=v[i]+v[j]+v[q];
			   w[k].x=i;
			   w[k].y=j;
			   w[k].z=q;
			 }
		 }
	}
	sort(w+1,w+n*n*n+1,cmp);
	OK=1;
	for(q=1;q<=n*n*n&&OK==1;q++)
	{	t=S-w[q].s;
		i=1;
		j=n*n*n;
		while(i<=j&&OK==1)
		{	m=(i+j)/2;
			if(w[m].s==t) { OK=0; g<<w[q].x<<" "<<w[q].y<<" "<<w[q].z<<" "<<w[m].x<<" "<<w[m].y<<" "<<w[m].z; }
			else
			{	if(w[m].s>t) j=m-1;
				if(w[m].s<t) i=m+1;
			}
		}
	}
	if(OK==1) g<<-1;
	f.close();
	g.close();
	return 0;
}