Cod sursa(job #2745075)

Utilizator DianaIfrosaIfrosa Diana DianaIfrosa Data 25 aprilie 2021 20:39:26
Problema Loto Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");

long long n,S,val[101];
pair <int,int> sume[6000];
int ct;
bool comp(pair <int,int> A, pair <int,int> B)
{

    return A.first+A.second<=B.first+B.second;

}
pair<int,int> Cauta(int st,int dr,int sum) //cauta binar suma data in array ul sume
{
    if(st<=dr)
    {
        int m=(st+dr)/2;

        if(sume[m].first+sume[m].second==sum)
             return sume[m];
        else if(sume[m].first+sume[m].second<sum)
            Cauta(m+1,dr,sum);
        else
           Cauta(st,m-1,sum);

    }
    else
        return make_pair(-1,-1); //nu s-a putut gasi



}
int main()
{
    pair<int,int> rez;
    bool ok=0;

    fin>>n>>S;
    for(int i=0; i<n; ++i)
        fin>>val[i];

    for(int i=0; i<n; ++i)
        for(int j=i; j<n; ++j)
            sume[ct++]=make_pair(val[i],val[j]);


    sort(sume,sume+ct,comp);     //sorteaza crescator sumele

    for(int i=0; i<ct && !ok; ++i)
        for(int j=i; j<ct; ++j)
            if(sume[i].first+sume[i].second+sume[j].first+sume[j].second<=S)
            {
                //cout<<S-sume[i].first-sume[i].second-sume[j].first-sume[j].second<<"\n";
                rez=Cauta(0,ct-1,S-sume[i].first-sume[i].second-sume[j].first-sume[j].second);
                if(rez.first!=-1)
                {
                    ok=1;
                    fout<<sume[i].first<<" "<<sume[i].second<<" "<<sume[j].first<<" "<<sume[j].second<<" "<<rez.first<<" "<<rez.second;
                    break;
                }

            }
            else break;

    if(!ok)
        fout<<-1;


    return 0;
}