Cod sursa(job #865848)

Utilizator TibixbAndrei Tiberiu Tibixb Data 27 ianuarie 2013 10:17:26
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>

using namespace std;

int v[110];
struct trei {
	int s;
	int a;
	int b;
	int c;
};

trei t[1000010];

int cmp(trei a, trei b) {
	return a.s < b.s;
	//return a.a+a.b+a.c < b.a+b.b+b.c
}

int n, nr, s, i, j, k, p, u, m, ok;

int main() {
	ifstream fin("loto.in");
	ofstream fout("loto.out");
	fin>>n>>s;
	for (i=1;i<=n;i++)
		fin>>v[i];
	
	for (i=1;i<=n;i++)
		for (j=i;j<=n;j++)
			for (k=j;k<=n;k++) {
				nr++;
				t[nr].s = v[i] + v[j] + v[k];
				t[nr].a = v[i];
				t[nr].b = v[j];
				t[nr].c = v[k];
			}

	sort(t+1, t+nr+1, cmp);
	
	ok = 0;
	for (i=1;i<=nr && ok == 0;i++) {
		if (t[i].s <= s) {
			p = i;
			u = nr;
			while (p<=u) {
				m = (p+u)/2;
				if (t[m].s == s-t[i].s) {
					fout<<t[i].a<<" "<<t[i].b<<" "<<t[i].c<<" "<<t[m].a<<" "
						<<t[m].b<<" "<<t[m].c<<"\n";
					
					ok = 1;
					break;
				}
				if (t[m].s > s-t[i].s)
					u = m-1;
				else
					p = m+1;
			}
		}
	}		
	
	if (ok == 0)
		fout<<"-1\n";
	
	return 0;
}