Cod sursa(job #2013671)

Utilizator frodobiosif aug frodob Data 22 august 2017 00:52:08
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

class Element{
public:
	int a;
	int b;
	int c;
	int s;
	Element() {};
	void set(int i, int j, int k){
		a=i;b=j;c=k;
		s = a+b+c;
	};
};
// ordering function
bool elemComp (Element x,Element y) {return (x.s<y.s);}
// binary search
int bin_search(int val, int left0, int right0);
//globals
Element* vsum;
int n;
int main(void) {
	int s = 0, sp;
    int nmax;
    int numbers[101];
	int i,j,k;
	fstream infile("loto.in", ios::in);
	fstream outfile("loto.out", ios::out);

	// read n, s
	infile>>n>>s;
	// read numbers
	for(i=0;i<n; ++i) 
		infile>>numbers[i];
	// alloc vsum
	vsum = new Element[n*n*n];

	// compute sums
	nmax = 0;
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			for(k=0;k<n;++k)
				vsum[nmax++].set(numbers[i], numbers[j], numbers[k]);
    // sort
	sort(vsum, vsum+nmax-1, elemComp);
	//
	if ((s>=2*vsum[0].s) && (s<=2*vsum[nmax-1].s)) {
	    int ip=0;
	    for(sp=vsum[0].s;sp<=s ;++sp) {
		    i = bin_search(sp, ip, nmax);
		    if (i!=-1) {
			    ip = i;
			    j = bin_search(s-sp, i, nmax);
			    if (j!=-1) {
			        outfile<<int(vsum[i].a)<<" "<<int(vsum[i].b)<<" "<<int(vsum[i].c)<<" "
				          <<int(vsum[j].a)<<" "<<int(vsum[j].b)<<" "<<int(vsum[j].c);
					delete[] vsum;
			        infile.close();
	                outfile.close();
		            return 0;
			    }
		    }
        }
	}
    // not found
	outfile<<"-1";

	delete[] vsum;
	infile.close();
	outfile.close();
	return 0;
}

int bin_search(int x, int left0, int right0) {
	int left = left0;
	int right = right0-1;
	int middle;
	while(left <= right) {
		middle = (left+right)/2;
		if (vsum[middle].s==x)
			return middle;
		else if (x<vsum[middle].s)
			right = middle-1;
		else
			left = middle+1;
	}
	return -1;
}