Cod sursa(job #2746689)

Utilizator MihaelaDanilaDanila Mihaela MihaelaDanila Data 28 aprilie 2021 12:11:04
Problema Loto Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.52 kb

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream f("loto.in");
ofstream g("loto.out");

bool posibil = false;
long n,S;
vector<long> numerePosibile;
vector<long> rezultate;
vector<long> sol;
vector<long>::iterator it;
vector<long>::iterator go;

int main(){
    long x,rest;
    f>>n>>S;
    for(int i=0;i<n;i++){
        f>>x;
        numerePosibile.push_back(x);
    }
            //fac vectorul cu toate sumele partiale
    for(int i=0;i<numerePosibile.size();i++){
        for(int j=i;j<numerePosibile.size();j++){
            for(int k=j;k<numerePosibile.size();k++){
                int sumaCurenta;
                sumaCurenta = numerePosibile[i]+numerePosibile[j]+numerePosibile[k];
                rezultate.push_back(sumaCurenta);
            }
        }
    }
            //sortez sumele posibile
    sort(rezultate.begin(), rezultate.end());

    for(it=rezultate.begin();it!=rezultate.end()&&posibil==false;it++){
        rest = S-*it;
                //cautare binara in vectorul de sume
        int st,dr,mij;
        st = 0;
        dr = rezultate.size();
        while(st <= dr){
            mij = (st + dr) / 2;
            if(rezultate[mij] == rest){
                posibil = true;
                break;
            }
            if(rest<rezultate[mij]) dr = mij-1;
            else st = mij+1;
        }

    }

    if(posibil){
        for(int i=0;i<numerePosibile.size();i++){
            for(int j=i;j<numerePosibile.size();j++){
                for(int k=j;k<numerePosibile.size();k++){
                    int sumaCurenta;
                    sumaCurenta = numerePosibile[i]+numerePosibile[j]+numerePosibile[k];
                    if(sumaCurenta == rest){
                        sol.push_back(numerePosibile[i]);
                        sol.push_back(numerePosibile[j]);
                        sol.push_back(numerePosibile[k]);
                    }
                    if(sumaCurenta == S-rest){
                        sol.push_back(numerePosibile[i]);
                        sol.push_back(numerePosibile[j]);
                        sol.push_back(numerePosibile[k]);
                    }
                }
            }
        }
        sort(sol.begin(), sol.end());
        for(it=sol.begin();it!=sol.end();it++){
            g<<*it<<" ";
        }
    }else{
        g<<-1;
    }
/*
    for(it=rezultate.begin();it!=rezultate.end();it++){
        cout<<*it<<" ";
    }
*/
    return 0;
}