Pagini recente » Cod sursa (job #1888694) | Cod sursa (job #8830) | Cod sursa (job #1752662) | Cod sursa (job #1795537) | Cod sursa (job #2738525)
#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;
}