Cod sursa(job #2504735)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 5 decembrie 2019 14:29:23
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

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

int ok=0,n,S,v[105];

struct Type
{
    int Sum,a,b,c;
};

vector <Type> sol;

bool Comp(Type a, Type b)
{
    return a.Sum<b.Sum;
}

int main()
{
    fin>>n>>S;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    for(int k=1;k<=n;k++)
    {
        for(int i=k;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                int aux=v[i]+v[j]+v[k];
                sol.push_back({aux,v[i],v[j],v[k]});
            }
        }
    }
    for(unsigned i=0;i<sol.size();i++)
    {
        int aux=S-sol[i].Sum;
        int soln=-1,left=0,right=sol.size()-1;
        while(left<=right)
        {
            int mij=(left+right)/2;
            if(sol[mij].Sum==aux)
            {
                soln=mij;
                break;
            }
            if(sol[mij].Sum>aux)
                right=mij-1;
            if(sol[mij].Sum<aux)
                left=mij+1;
        }
        if(soln>=0)
        {
            ok=1;
            fout<<sol[i].a<<" "<<sol[i].b<<" "<<sol[i].c<<" ";
            fout<<sol[soln].a<<" "<<sol[soln].b<<" "<<sol[soln].c<<" ";
            break;
        }
    }
    if(!ok)
        fout<<-1<<'\n';
}