Cod sursa(job #2894198)

Utilizator AncaGAncuta Gava AncaG Data 27 aprilie 2022 14:59:46
Problema Loto Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <iostream>
#include <fstream>
#include <unordered_map>

using namespace std;

//struct triplet_suma{
//    int index1, index2, index3;
//};
//unordered_map <int, triplet_suma> sume_loto; -> am incercat cu un struct dar mai bine fara

// ma intereseaza toate combinatiile de 3 nr si suma lor pe fiecare combinatie-> am 112 dar nu si 121 deci sunt combinari
// ca mai apoi sa refolosesc aceste sume pentru a "completa" suma target castigatoare
// am 6 nr (cu repetitii) care imi compun suma castigatoare
// practic  rup suma castigatoare in 2 sume pe care le vad din combinatiile de mai sus mentionate

// tripletul de nr va fi valoare in hash table iar key-ul este de fapt suma data de triplet

// in final voi cauta  sa completez acea suma castigatoare si voi afisa  implicit 2 randuri de triplete asociate sumei finale castigatoare

unordered_map<int, tuple<int, int, int>> sume_loto;

int main()
{
    ifstream input("loto.in");
    ofstream output("loto.out");

    int numere[101];
    int n, S;
    input>> n >> S;

    for(int i = 0; i < n; i++){
        input>>numere[i];
    }
// am combinari de n=cate nr am in input  luate cate k= 3 (triplet ales pentru a vedea cobinatiile de sume formate de 3 nr)
    for(int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            for (int k = j; k < n; k++) {
                sume_loto[numere[i] + numere[j] + numere[k]] = make_tuple(numere[i], numere[j], numere[k]);
            }
        }
    }

    unordered_map<int, tuple<int, int, int>>::iterator itr;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            for(int k = j; k < n; k++){
  //iteratorul ma ajuta sa parcurg hash table-ul in functie de ce imi mai trebuie pentru a completa suma castigatoare si sa verific daca exista o astfel de combinatie
                itr = sume_loto.find(S-(numere[i]+numere[j]+numere[k]));
  // daca nu se gaseste acea valoare in hash si ajunge la final atunci reintra in for-ul principal
                        if(itr == sume_loto.end())
                        {
                            continue;
                        }
   //altfel  pot afla cu val sumei ramase si celelate 3 valorile hashuite care imi mai trebuie
                        else
                        {   int suma_combinatie = numere[i]+numere[j]+numere[k];
                            // imi iau valorile din tuplu una cate una
                            output<<get<0>(sume_loto[suma_combinatie])<<" "<<get<1>(sume_loto[suma_combinatie])<<" "<<get<2>(sume_loto[suma_combinatie])<<" "
                                <<get<0>(sume_loto[S-suma_combinatie])<<" "<<get<1>(sume_loto[S-suma_combinatie])<<" "<<get<2>(sume_loto[S-suma_combinatie]);
                            return 0;
                        }
                    }
                }
            }

    output<<-1;
    input.close();
    output.close();
}