Cod sursa(job #2014117)

Utilizator frodobiosif aug frodob Data 22 august 2017 22:00:50
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
class Element{
public:
    int a;
    int b;
    int c;
    int s;
	Element() {};
};
// ordering function
bool elemComp (Element x,Element y) {return (x.s<y.s);}
// binary search
int bin_search(int val, int left0, int right0);
int get_idx_max(int x, int left0, int right0);
//globals
Element* vsum;
int n;
int main(void) {
    int s = 0, sp;
    int nmax;
	int nsum;
    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];
    }
    vsum = new Element[n*n*n];
    // compute sums
	nsum = 0;
    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)) {
                    vsum[nsum].a = numbers[i];vsum[nsum].b = numbers[j];vsum[nsum].c = numbers[k];
                    vsum[nsum].s = sp;
					nsum++;
                }
            }
    // sort
    sort(vsum, vsum+nsum, elemComp);
	nmax = get_idx_max(s/2+1,0,nsum);
    for(i=0;i<nmax+1;++i) {
        if((i>0) && (vsum[i-1].s==vsum[i].s))
            continue;
        j = bin_search(s-vsum[i].s, i, nsum);
        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;
}

int get_idx_max(int x, int left0, int right0) {
    int left = left0;
    int right = right0-1;
    int middle = left0;
    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 middle+1;
}