Cod sursa(job #518798)

Utilizator dacyanMujdar Dacian dacyan Data 3 ianuarie 2011 05:24:50
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define INF 102
using namespace std;

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

struct S {
	long long nr1, nr2, nr3, sum;
}a[INF*INF*INF];

long long s, n, su, b[INF], k1, k2;
bool ok;

void Back(int k);
void Write();
bool Calc(S a, S b);

int main()
{
	fin >> n >> s;
	for (int i = 1; i <= n; ++i)
		fin >> b[i];
	fin.close();
	
	long c = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			for (int k = 1; k <= n; ++k)
			{
				c++;
				a[c].nr1 = b[i];
				a[c].nr2 = b[j];
				a[c].nr3 = b[k];
				a[c].sum = b[i] + b[j] + b[k];
			}
	sort(a + 1, a + c + 1, Calc);
	long long st, dr, mij;
	for (long i = 1; i <= c && !ok; ++i)
	{
		su = s - a[i].sum;
		st = 0; dr = s;
		while (st <= dr)
		{
			mij = (st + dr) / 2;
			if (a[mij].sum == su)
			{
				ok = true;
				k1 = i; 
				k2 = mij;
				break;
			}
			if (a[mij].sum > su) st = mij + 1;
			if (a[mij].sum < su) dr = mij - 1;
		}
	}
	
	if (!ok) fout << "-1" << '\n';
	else
		fout << a[k1].nr1 << ' ' << a[k1].nr2 << ' ' << a[k1].nr3 << ' ' << a[k2].nr1 << ' ' << a[k2].nr2 << ' ' << a[k2].nr3; 
	fout.close();
	return 0;
}

bool Calc (S a, S b)
{
	return a.sum < b.sum;
}