Cod sursa(job #2745263)

Utilizator DianaIfrosaIfrosa Diana DianaIfrosa Data 26 aprilie 2021 11:27:22
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>

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

const int P=49157;
int n,S,val[101];
int ct;

vector< tuple<int,int,int> > hashsum[P]; //pun in hash sumele de cate 3
tuple <int,int,int> sume[1000001]; //pastrez tupluri cu combinarile de cate 3 valori

void Adauga(tuple <int,int,int> t, int poz)
{
    hashsum[poz].push_back(t);

}

bool Cauta(int sum, int pozpereche)
{
    int poz=sum%P;

    for(int i=0; i<hashsum[poz].size(); ++i)
        if(get<0>(hashsum[poz][i]) + get<1>(hashsum[poz][i]) + get<2>(hashsum[poz][i])==sum)
        {

            fout<<get<0>(hashsum[poz][i])<<" "<<get<1>(hashsum[poz][i])<<" "<<get<2>(hashsum[poz][i])<<" "<<get<0>(sume[pozpereche])<<" "<<get<1>(sume[pozpereche])<<" "<<get<2>(sume[pozpereche])<<"\n";
            return 1;
        }

    return 0; //nu s-a gasit pereche

}

int main()
{
    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)
            for(int k=j; k<n; ++k)
                if(val[i]+val[j]+val[k]<=S) //adaug in hash doar daca suma lor e <=S
                {
                    Adauga(make_tuple(val[i],val[j],val[k]), (val[i]+val[j]+val[k])%P);
                    sume[ct++]=make_tuple(val[i],val[j],val[k]);
                }


    for(int i=0; i<ct; ++i) //iau toate tuplurile de cate 3
    {
        ok=Cauta(S-get<0>(sume[i])-get<1>(sume[i])-get<2>(sume[i]), i ); //caut diferenta
        if(ok)
            break;
    }

    if(!ok)
        fout<<-1;

    return 0;
}