Cod sursa(job #974501)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 17 iulie 2013 13:26:02
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
//O( (n^3)log(n^3) )
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<unsigned, unsigned short > ENTRY_T;

int bsearch(const vector<ENTRY_T> &sume,unsigned size, unsigned val){
    unsigned lo=0, hi=size-1;
    unsigned mid;
    bool found=false;
    while(lo<=hi&&!found){
        mid=lo+(hi-lo)/2;
        if(sume[mid].first<val) lo=mid+1;
        else if(sume[mid].first==val){found=true;}
        else hi=mid-1;
    }
    if(found) return mid;
    else return -1;
}

int main(){
    ifstream fin("loto.in");
    ofstream fout("loto.out");

    unsigned N,S;
    fin>>N>>S;

    vector<unsigned> numere(N);
    for(unsigned i=0;i<N;++i) fin>>numere[i];

    vector<ENTRY_T> sume(N*N*N);

    unsigned c=0;
    for(unsigned short i=0;i<N;++i)
        for(unsigned short j=i;j<N;++j)
            for(unsigned short k=j;k<N;++k){
                sume[c].first=numere[i]+numere[j]+numere[k];
                sume[c].second=(i<<8)|j;
                ++c;
            }

    sort(sume.begin(),sume.begin()+c);

    bool found=false;
    for(unsigned i=0;i<c&&(!found)&&sume[i].first<=S;++i){
        int y=bsearch(sume,c,S-sume[i].first);
        if(y>-1){
            found=true;
            vector<unsigned> out(6);
            out[0]=numere[ (sume[i].second)>>8 ];
            out[1]=numere[ (sume[i].second)&255 ];
            out[2]=sume[i].first-out[0]-out[1];
            out[3]=numere[ (sume[y].second)>>8 ];
            out[4]=numere[ (sume[y].second)&255 ];
            out[5]=sume[y].first-out[3]-out[4];
            sort(out.begin(),out.end());
            fout<<out[0]<<' '<<out[1]<<' '<<out[2]<<' '<<out[3]<<' '<<out[4]<<' '<<out[5]<<'\n';
        }
    }
    if(!found) fout<<"-1\n";
    return 0;
}