Cod sursa(job #568142)

Utilizator tudorsTudor Siminic tudors Data 30 martie 2011 20:49:12
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int i,n,j,k,poz;
int REZ[7],V[101];
long long S;
typedef struct {long long s;int a,b,c;} SUMA;
SUMA A[1000001];
FILE *f,*g;

void citire()
{
	fscanf(f,"%d %lld",&n,&S);
	for (int i=1;i<=n;i++)
		fscanf(f,"%d",&V[i]);
}

int cmp(SUMA a, SUMA b)
{
	return (a.s<b.s);
}

int bs(long long x)
{
	int st=1,dr=poz;
	while (st<=dr)
		if (x==A[(st+dr)/2].s)
			return (st+dr)/2;
		else if (x<A[(st+dr)/2].s)
			dr=(st+dr)/2-1;
		else
			st=(st+dr)/2+1;
	return 0;
}

int main()
{
	f=fopen("loto.in","r");
	g=fopen("loto.out","w");
	citire();
	for (i=1;i<=n;++i)
		for (j=i;j<=n;++j)
			for (k=j;k<=n;++k)
			{
				A[++poz].s=V[i]+V[j]+V[k];
				A[poz].a=V[i];
				A[poz].b=V[j];
				A[poz].c=V[k];
			}
	sort(A+1,A+poz+1,cmp);
	for (i=1;i<=poz;i++)
		if (k=bs(S-A[i].s))
		{
			REZ[0]=A[i].a;
			REZ[1]=A[i].b;
			REZ[2]=A[i].c;
			REZ[3]=A[k].a;
			REZ[4]=A[k].b;
			REZ[5]=A[k].c;
			sort(REZ+1,REZ+6);
			for (j=0;j<=5;j++)
				fprintf(g,"%d ",REZ[j]);
			return 0;
		}
	fprintf(g,"%d",-1);
	fclose(f);
	fclose(g);
	return 0;
}