Cod sursa(job #157647)

Utilizator gigi_becaliGigi Becali gigi_becali Data 13 martie 2008 10:23:31
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
//(c) Marina
//loto - infoarena
//Complexitate: O(N^3)
//Memorie: O(N^3)

using namespace std;
#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;

struct cmp{
	bool operator()(const suma &a, const suma &b)const
	{
		if(a.s<b.s)return 1;
		return 0;
	}
};

inline int caut(int val)
{
	int i,cnt;
	int a=0, b=nr;
	for(i=1, cnt=(1<<20); cnt ; cnt>>=1)
		if(i+cnt<=b)
			if(sum[i+cnt].s<=val) i+=cnt;
	if(sum[i].s==val) return i;
	return 0;

	
	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,cmp());
	
	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;
}