Cod sursa(job #596724)

Utilizator maritimCristian Lambru maritim Data 18 iunie 2011 15:33:35
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define MaxN 110
#define MaxN3 1000100
#define ll long long

typedef struct
{
	int val;
	int a;
	int b;
	int c;
} sols;

int A[MaxN];
sols B[MaxN3];
int N;
int S;
int nr;
int sol1;
int sol2;

bool cmp(sols a,sols b)
{
	return a.val < b.val;
}

int binary_search(int li,int ls,int a)
{
	if(li <= ls)
	{
		if(B[(li + ls) / 2].val == a)
			return (li + ls) / 2;
		else if(B[(li + ls) / 2].val > a)
			return binary_search(li , (li + ls) / 2 - 1 , a);
		else
			return binary_search((li + ls) / 2 + 1 , ls , a);
	}
	return 0;
}

void solve(void)
{
	bool gata = false;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			for(int k=1;k<=N;k++)
			{
				B[++nr].val = A[i] + A[j] + A[k];
				B[nr].a = A[i];
				B[nr].b = A[j];
				B[nr].c = A[k];
			}
	sort(B+1,B+nr+1,cmp);
	for(int i=1;i<=nr && !gata;i++)
		if(sol2 = binary_search(1,nr,S-B[i].val))
		{
			gata = true;
			sol1 = i;
		}
}

int main()
{
	FILE *f = fopen("loto.in","r");
	FILE *g = fopen("loto.out","w");
	
	fscanf(f,"%d %llu",&N,&S);
	for(int i=1;i<=N;i++)
		fscanf(f,"%d ",&A[i]);
	solve();
	if(sol1)
		fprintf(g,"%d %d %d %d %d %d",B[sol1].a,B[sol1].b,B[sol1].c,B[sol2].a,B[sol2].b,B[sol2].c);
	else
		fprintf(g,"-1");
	
	fclose(g);
	fclose(f);
	return 0;
}