Cod sursa(job #748555)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 13 mai 2012 18:57:31
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<iostream>
#include<fstream>
#include<cstdlib>

using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

struct loto
{
	long suma, x, y, z;
} d[101 * 101 * 101];

long v[101];

int compare(const void * a, const void * b)
{
	loto *pa, *pb;
	pa = (loto*) a;
	pb = (loto*) b;
	
	if((pa -> suma) > (pb -> suma))
		return 1;
	
	if((pa -> suma) < (pb -> suma))
		return -1;
	
	return 0;
}

int cauta(int val, int dr)
{
	if(val < 0)
		return 0;
	
	int st = 1, med;
	
	while(st <= dr){
		med = (st + dr) >> 1;
		
		if(val == d[med].suma)
			return med;
		
		if(val < d[med].suma)
			dr = med - 1;
		else
			st = med + 1;
	}
	
	return 0;
}

int main()
{
	int n, i, j, k;
	long s, u = 0, val;
	
	in >> n >> s;
	
	for(i = 1; i <= n; ++i)
		in >> v[i];
	
	for(i = 1; i <= n; ++i)
		for(j = i; j <= n; ++j)
			for(k = j; k <= n; ++k){
				d[ ++u ].suma = v[i] + v[j] + v[k];
				d[u].x = v[i];
				d[u].y = v[j];
				d[u].z = v[k];
			}
			
	qsort(d + 1, u, sizeof(d[0]), compare);
	
	for(i = 1; i <= u; ++i){
		val = cauta(s - d[i].suma, u);
		if(val){
			out << d[i].x << " " << d[i].y << " " << d[i].z << " " << d[val].x << " " << d[val].y << " " << d[val].z;
			return 0;
		}
	}
	
	out << "-1";
	
	return 0;
}