Pagini recente » Cod sursa (job #2821402) | Cod sursa (job #2779394) | Cod sursa (job #978003) | Cod sursa (job #2466276) | Cod sursa (job #396307)
Cod sursa(job #396307)
#include <fstream>
#include <algorithm>
using namespace std;
const int NMax = 1 << 7;
const int AMax = 1 << 20;
int N, S, v[NMax], a[AMax]; // memorez in a toate sumele ce se pot forma din 3 termeni
ifstream f("loto.in");
ofstream o("loto.out");
bool comp (int a, int b) {
return a < b;
}
void afisare (int x) { // cand am gasit cele 2 sume de trei termeni = S le afisez pe rand gasid tre temeni care sunt egali cu x=s[i]
for (int i = 1; i <= N; ++i) {
for (int j = i; j <= N; j++) {
for (int k = j; k <= N; ++k) {
if (v[i] + v[j] + v[k] == x) {
o<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
return;
}
}
}
}
}
int BS (int m) {//cauta o suma de trei termeni astefel incat s[gasit] = S - s[dat]
int i, step;
for (step = 1; step < v[0]; step <<= 1) {}
for (i = 0; step; step >>= 1) {
if (i + step <= v[0] && a[i + step] <= S - a[m]) {
i += step;
}
}
if (a[i] == S - a[m]) { // dc gaseste afiseaza cele 2 sume : s[gasit] shi s[dat] shi returneaza 1
afisare(a[i]);
afisare(a[m]);
return 1;
}
return -1; // altfel returneaza -1
}
int main () {
f>>n>>s;
for (int i = 1; i <= N; ++i) {
f>>v[i];
}
sort (v + 1, v + 1 + n, comp); // sortez sumele (dc nu faci asta iei 5 pct)
for (int i = 1; i <= N; ++i) { // generez in a toate sumele de 3 termeni POSIBILE
for (int j = i; j <= N; ++j) {
for (int k = j; k <= N; ++k) {
a[++v[0]] = v[i] + v[j] + v[k];
}
}
}
for (int m = 1; m <= v[0]; ++m) {
if (BS (m) == 1) { // dc BS returneaza 1 inseamna ca a gasit sol shi a afisat-o deci programul se opreste
return 0;
}
}
o<<"-1\n";// dc programul nu a gasit sol shi nu s-a oprit afisez -1
return 0;
}