Cod sursa(job #2738547)

Utilizator MateiDorian123Nastase Matei MateiDorian123 Data 6 aprilie 2021 00:16:20
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
/* Idee: vom profita de faptul ca mereu se aleg 6 numere. Facem toate combinatiile posibile de cate 3 numere si le memoram intr un hash. Parcurgem cheile din
hash si verificam daca valoarea suma - cheia_curenta se afla in hash. Daca am gasit valoarea cautata afisam solutia, daca nu afisam -1
Complexitate O(n^3), dar n ul e 100 deci e ok*/

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

int n, s;
int v[105];

struct element{
    int t1, t2, t3;
}; /// pentru fiecare element din hash vom memora si termenii din suma pentru a reconstitui solutia -> t1 + t2 + t3 = suma

unordered_map<int, element> f; /// tabela de dispersie sub forma unui dictionar in care cheia e suma si valoarea e un tuplu cu termenii sumei

void Citire(){
    fin>>n>>s;

    for(int i = 1; i <= n; i ++)
        fin>>v[i];
    fin.close();
}

void Rezolva(){
    int i, j, k, sum;
    element el;

    for(i = 1; i <= n; i ++)
        for(j = i; j <= n; j ++)
            for(k = j; k <= n; k ++)
            {
                sum = v[i] + v[j] + v[k];
                el.t1 = v[i];
                el.t2 = v[j];
                el.t3 = v[k];
                f[sum] = el; /// adaugam elementul in map

            }

    for(auto it = f.begin(); it!=f.end(); it++)
        {   int wanted = s - it->first; /// it->first = cheia / it->second = valoarea
            if(f.count(wanted) > 0){ /// documentatie: http://www.cplusplus.com/reference/unordered_map/unordered_map/count/ -> count returneaza 1 daca exista cheia
                fout<<it->second.t1<<" "<<it->second.t2<<" "<<it->second.t3<<" "<<f[wanted].t1<<" "<<f[wanted].t2<<" "<<f[wanted].t3;
                return;
            }
        }

    fout<<-1;
}

int main()
{
    Citire();
    Rezolva();
    fout.close();
    return 0;
}