Cod sursa(job #2738525)

Utilizator MateiDorian123Nastase Matei MateiDorian123 Data 5 aprilie 2021 23:33:40
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 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 = i + j + k;
                el.t1 = i;
                el.t2 = j;
                el.t3 = k;
                if(sum <= s)
                    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
            unordered_map<int, element>:: const_iterator found;

            found = f.find(wanted);  /// documentatie find : http://www.cplusplus.com/reference/unordered_map/unordered_map/find/
            if(found != f.end()){ /// find-ul intoarce f.end() daca nu a gasit elementul
                fout<<it->second.t1<<" "<<it->second.t2<<" "<<it->second.t3<<" "<<found->second.t1<<" "<<found->second.t2<<" "<<found->second.t3;
                return;
            }
        }

    fout<<-1;
}

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