Cod sursa(job #455444)

Utilizator darrenRares Buhai darren Data 13 mai 2010 20:08:18
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
#include<algorithm>
using namespace std;

typedef long long int64;

ofstream fout("loto.out");
struct tri
{
	int64 a, b, c;
};

void read();
void doit();
int64 src(long long val);

long long n, sm, v[101];
long long s[10000001], t = -1;
tri tt[1001];

int main()
{
	read();
	doit();
	fout.close();
	return 0;
}

void read()
{
	ifstream fin("loto.in");
	fin >> n >> sm;
	for (long long i = 0; i < n; ++i)
		fin >> v[i];
	fin.close();
}

void doit()
{
	for (int64 i = 0; i < n; ++i)
		for (int64 j = 0; j < n; ++j)
			for (int64 k = 0; k < n; ++k)
			{
				s[++t] = v[i] + v[j] + v[k];
				tt[t].a = i, tt[t].b = j, tt[t].c = k;
			}
	sort(s, s + t + 1);
	for (int64 i = 0; i <= t; ++i)
		if (src(sm - s[i]) != -1)
		{
			int64 ps = src(sm - s[i]);
			fout << v[tt[i].a] << ' ' << v[tt[i].b] << ' ' << v[tt[i].c] << ' '
			     << v[tt[ps].a] << ' ' << v[tt[ps].b] << ' ' << v[tt[ps].c];
			return;
		}
	fout << -1;
}

int64 src(long long val)
{
	int64 l1 = 0, l2 = t, p = -1;
	while (l1 <= l2)
	{
		int64 md = (l1 + l2) >> 1;
		if (s[md] == val)
		{
			p = md;
			break;
		}
		if (s[md] > val)
			l2 = md - 1;
		else
			l1 = md + 1;
	}
	return p;
}