Cod sursa(job #2013272)

Utilizator frodobiosif aug frodob Data 20 august 2017 23:38:23
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

class Element{
public:
	int a;
	int b;
	int c;
	int s;
	Element(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
vector<Element> vsum;
int n;
int main(void) {
	int s = 0, sp;
    int nmax;
    int numbers[101];
	int i,j,k;
	int min = 0;
	int max = 600000001;
	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];
		if (numbers[i]<min)
			min = numbers[i];
		else if (numbers[i]>max)
			max = numbers[i];
	}

	// compute sums
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			for(k=0;k<n;++k) {
				sp = numbers[i]+numbers[j]+numbers[k];
			    if ((sp+3*max>=s) && (sp+3*min<=s)) {
				    Element elm(numbers[i], numbers[j], numbers[k]);
				    vsum.push_back(elm);
				}
			}
    // sort
	sort(vsum.begin(), vsum.end(), elemComp);
	//
	nmax = vsum.size();
	for(i=0;i<nmax && 2*vsum[i].s<=s ;++i) {
		if((i>0) && (vsum[i-1].s==vsum[i].s))
			continue;
		j = bin_search(s-vsum[i].s, 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);
			infile.close();
	        outfile.close();
		    return 0;
		}
    }
    // not found
	outfile<<"-1";

	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;
}