Cod sursa(job #2555622)

Utilizator DunareanuDinu Dunareanu Dunareanu Data 24 februarie 2020 10:29:42
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <algorithm>

FILE *fin , *fout;

using namespace std;

int nr[100];

struct ura {
    int suma,a,b,c;
};

ura v[666015];

bool ord(ura a, ura b) {
    if(a.suma<b.suma) {
        return true;
    }
    else {
        return false;
    }
}

int cb(int st, int dr, int e) {
    int mij;
    while(dr-st>1) {
        mij=(st+dr)/2;
        if(v[mij].suma>e) {
            dr=mij;
        }
        else {
            st=mij;
        }
    }
    return st;
}

int main() {
    fin=fopen("loto.in","r");
    fout=fopen("loto.out","w");

    int n,s,i,sum,j,k,cs=0,f=0,poz;
    fscanf(fin,"%d%d",&n,&s);
    for(i=0;i<n;i++) {
        fscanf(fin,"%d",&nr[i]);
    }

    for(i=0;i<n;i++) {
        for(j=i;j<n;j++) {
            for(k=j;k<n;k++) {
                sum=nr[i]+nr[j]+nr[k];
                if(sum<=s) {
                    v[cs].suma=sum;
                    v[cs].a=nr[i];
                    v[cs].b=nr[j];
                    v[cs].c=nr[k];
                    cs++;
                }
            }
        }
    }

    sort(v,v+cs,ord);

    i=0;
    while(f==0 && i<cs) {
        poz=cb(i,cs,s-v[i].suma);
        if(v[i].suma+v[poz].suma==s) {
            f=1;
        }
        else {
            i++;
        }
    }

    if(f==1) {
        fprintf(fout,"%d %d %d %d %d %d\n",v[i].a,v[i].b,v[i].c,v[poz].a,v[poz].b,v[poz].c);
    }
    else {
        fprintf(fout,"-1\n");
    }

    fclose(fin);
    fclose(fout);
    return 0;
}