Cod sursa(job #2046639)

Utilizator DawlauAndrei Blahovici Dawlau Data 23 octombrie 2017 22:47:20
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
const int NMAX=105;
struct components_of_sum{
    int x1,x2,x3;
    int the_sum;
};
bool cmp(const components_of_sum&a,const components_of_sum&b){
    return a.the_sum<b.the_sum;
}
int n,nrsums,s;
int v[NMAX],sol[NMAX];
components_of_sum sum[NMAX];
void read_data(){
    int i;
    for(i=1;i<=n;++i)
        fin>>v[i];
}
void preprocess_sums(){
    int i,j,k;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            for(k=1;k<=n;++k)
                sum[++nrsums]={v[i],v[j],v[k],v[i]+v[j]+v[k]};
    sort(sum+1,sum+1+nrsums,cmp);
}
int bs(int x){
    int st=1,dr=nrsums,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(sum[mij].the_sum==x)
            return mij;
        else if(sum[mij].the_sum<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return -1;
}
void create_solution(){
    int i,j,k,a,poz;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            for(k=1;k<=n;++k){
                a=v[i]+v[j]+v[k];
                poz=bs(s-a);
                if(poz!=-1){
                    sol[1]=v[i];
                    sol[2]=v[j];
                    sol[3]=v[k];
                    sol[4]=sum[poz].x1;
                    sol[5]=sum[poz].x2;
                    sol[6]=sum[poz].x3;
                }
            }
}
void print(){
    if(!sol[1])
        fout<<-1;
    else{
        sort(sol+1,sol+7);
        int i;
        for(i=1;i<=6;++i)
            fout<<sol[i]<<' ';
    }
}
int main(){
    fin>>n>>s;
    read_data();
    preprocess_sums();
    create_solution();
    print();
}