Pagini recente » Cod sursa (job #846595) | Cod sursa (job #2255499)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
// Valoarea maxima a unui numar de la loterie
#define MAX_NR 100000
// Valoarea maxima a unei sume de 3 numere
#define MAX_SUMA (3 * MAX_NR)
int v[100];
int n, s;
struct Suma {
int suma, a, b, c;
} sume[MAX_SUMA];
int lg;
void citire() {
ifstream in("loto.in");
in >> n >> s;
for (int i = 0; i < n; ++i) {
in >> v[i];
}
}
void adauga_suma(int a, int b, int c) {
sume[lg++] = {
a + b + c,
a, b, c,
};
}
int cauta_binar(int val, int st, int dr) {
while (st < dr) {
int mid = st + (dr - st) / 2;
if (val < sume[mid].suma) {
dr = mid - 1;
} else if (val > sume[mid].suma) {
st = mid + 1;
} else {
return mid;
}
}
return -1;
}
int main() {
citire();
// In O(n^3) facem o lista cu toate sumele de 3 termeni
// pe care le putem obtine
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
for (int k = j; k < n; ++k) {
adauga_suma(v[i], v[j], v[k]);
}
}
}
// Pentru a putea cauta binar sumele, le sortam in O(n log n)
sort(sume, sume + lg, [] (const Suma& a, const Suma& b) {
return a.suma < b.suma;
});
ofstream out("loto.out");
// For-ul se executa de maxim `MAX_SUMA` ori, pentru o eficienta totala de
// O(MAX_SUMA * log MAX_SUMA) = O(1)
for (int k = 0; k < lg; ++k) {
Suma curent = sume[k];
int diferenta = s - curent.suma;
// Cauta binar o suma care sa acopere diferenta, in O(log MAX_SUMA)
int i = cauta_binar(diferenta, 0, lg);
if (i != -1) {
Suma gasit = sume[i];
out << curent.a << ' ' << curent.b << ' ' << curent.c << ' '
<< gasit.a << ' ' << gasit.b << ' ' << gasit.c << '\n';
return 0;
}
}
out << -1 << '\n';
}