Cod sursa(job #182249)

Utilizator marinaMarina Horlescu marina Data 20 aprilie 2008 16:16:07
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
//loto - infoarena
//Complexitate: O(N^3logN^3)
//Memorie: O(N^3)

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

using namespace std;

int N, S;
int v[MAXN];
int sum[MAX];

int nr;

int caut(int val)
{
	int a = 0, b = nr;
	while(a <= b)
	{
		int mij = (a+b)/2;
		if(sum[mij] == val) return mij;
		else if(sum[mij] > val) b = mij-1;
		else a = mij+1;
	}
	return 0;
}

void afis(int val)
{
	int i, j, k;
	for(i = 1; i <= N; ++i)
		for(j = i; j <= N; ++j)
			for(k = j; k <= N; ++k)
				if(v[i] + v[j] + v[k] == val)
				{
					printf("%d %d %d", v[i], v[j], v[k]);
					return;
				}
	return;
}
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 = i; j <= N; ++j)
			for(k = j; k <= N; ++k)
				sum[++nr] = v[i] + v[j] + v[k];

	sort(sum+1, sum+nr+1);
	
	int ok = 0;
	for(i = 1; i <= nr && sum[i] <=S && !ok; ++i)
		if(caut(S-sum[i]))
		{
			ok = 1;
			afis(sum[i]);
			printf(" ");
			afis(S-sum[i]);
			printf("\n");
		}
	
	if(!ok) printf("-1\n");
	return 0;
}