Cod sursa(job #874440)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 8 februarie 2013 14:37:13
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>

#define DIM 101

using namespace std;

struct trei {
	int a;
	int b;
	int c;
	int s;
};


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

trei v[DIM*DIM*DIM];

int a[DIM];

int n, s, i, j, k, x, p, u, m, t;

int main() {
	ifstream fin("loto.in");
	ofstream fout("loto.out");
	fin>>n>>s;
	for (i=1;i<=n;i++)
		fin>>a[i];
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++) {
				t++;
				v[t].s = a[i]+a[j]+a[k];
				v[t].a = a[i];
				v[t].b = a[j];
				v[t].c = a[k];
			}
	sort(v+1, v+t+1, cmp);
	
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++) {
				x = s - (a[i] + a[j] + a[k]);
				//caut binar pe x in v
				p = 1;
				u = t;
				while (p<=u) {
					m = (p+u)/2;
					if (v[m].s == x) {
						fout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" ";
						fout<<v[m].a<<" "<<v[m].b<<" "<<v[m].c<<" ";
						return 0;
					}
					if (v[m].s > x) {
						u = m-1;
					} else {
						p = m+1;
					}
				}
			}
	fout<<-1;
	return 0;
}