Cod sursa(job #396314)

Utilizator mihai995mihai995 mihai995 Data 14 februarie 2010 21:31:33
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <algorithm>
 
using namespace std;
const int NMax = 1 << 7;
const int AMax = 1 << 20;
 
int N, S, v[NMax], a[AMax];
 
bool comp (int a, int b) {
    return a < b;
}
 
void afisare (int x) {
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; ++k) {
                if (v[i] + v[j] + v[k] == x) {
                    printf ("%d %d %d ", v[i], v[j], v[k]);
                    return;
                }
            }
        }
    }
}
 
int BS (int m) {
    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]) {
        afisare(a[i]);
        afisare(a[m]);
        return 1;
    }
    return -1;
}
 
int main () {
    freopen ("loto.in", "r", stdin);
    freopen ("loto.out", "w", stdout);
     
    scanf ("%d %d", &N, &S);
    for (int i = 1; i <= N; ++i) {
        scanf ("%d", &v[i]);
    }
     
    sort (v + 1, v + 1 + N, comp);
     
    for (int i = 1; i <= N; ++i) {
        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) {
           return 0;
       }
    }
   printf ("-1\n");
     
    return 0;
}