Cod sursa(job #159791)

Utilizator marinaMarina Horlescu marina Data 14 martie 2008 13:34:01
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
//loto - infoarena
//Complexitate: O(N^3logN^3)
//Memorie: O(N^3)

#include <stdio.h>
#include <stdlib.h>
//#include <algorithm>
#define INPUT "loto.in"
#define OUTPUT "loto.out"
#define MAXN 101
#define MAX 1000001

int N, S;
int v[MAXN];
struct suma
{
	int s, na, nb, nc;
}sum[MAX];

int nr;

int comp(const void *A,const void* B)
{
	int a = (*((suma*)A)).s;
	int b = (*((suma*)B)).s;
	if(a>b) return 1;
	if(a==b) return 0;
	return -1;
}

int caut(int val)
{
	int a = 0, b = nr;
	while(a <= b)
	{
		int mij = (a+b)/2;
		if(sum[mij].s == val) return mij;
		else if(sum[mij].s > val) b = mij-1;
		else a = mij+1;
	}
	return 0;
}
int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%d %d", &N, &S);
	int i;
	for(i = 1; i <= N; ++i) scanf("%d", &v[i]);
	
	int j, k;
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= N; ++j)
			for(k = 1; k <= N; ++k)
				sum[++nr].s = v[i] + v[j] + v[k],
				sum[nr].na = v[i],
				sum[nr].nb = v[j],
				sum[nr].nc = v[k];
	qsort(sum+1, nr, sizeof(sum[0]), comp);
//	sort(sum+1, sum+nr+1, comp());
	
	int ok = 0;
	for(i = 1; i <= nr && sum[i].s<=S && !ok; ++i)
	{
		int j;
		if(j = caut(S-sum[i].s))
		{
			ok = 1;
			printf("%d %d %d %d %d %d\n", sum[i].na, sum[i].nb, sum[i].nc, sum[j].na, sum[j].nb, sum[j].nc);
		}
	}
	
	if(!ok) printf("-1\n");
	return 0;
}