Cod sursa(job #912243)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 12 martie 2013 10:45:48
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <algorithm>

using namespace std;

FILE *f = fopen ("loto.in","r");
FILE *g = fopen ("loto.out","w");

const int MAX_N = 105;

struct sm {
    int val, t[3];
};

int n, S, a[MAX_N], cnt;
sm sum[MAX_N * MAX_N * MAX_N];

bool cmp(const sm i, const sm j) {
    return i.val < j.val;
}

void read() {
    fscanf (f, "%d %d", &n, &S);
    for (int i = 1; i <= n; i++)
        fscanf (f, "%d", &a[i]);
}

int binsearch(int V) {
    int lo = 1, hi = cnt, mid;

    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (sum[mid].val == V)
            return mid;
        else if (sum[mid].val > V)
            hi = mid - 1;
        else
            lo = mid + 1;
    }

    return -1;
}

void precompute() {
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            for (int k = j; k <= n; k++)
                if (a[i] + a[j] + a[k] <= S) {
                    cnt++;
                    sum[cnt].val = a[i] + a[j] + a[k];
                    sum[cnt].t[0] = a[i];
                    sum[cnt].t[1] = a[j];
                    sum[cnt].t[2] = a[k];
                }
    sort (sum + 1, sum + cnt + 1, cmp);
}

void solve() {
    int ok = 0;
    for (int i = 1; i <= cnt && !ok; i++) {
        int poz = binsearch(S - sum[i].val);
        if (poz != -1) {
            int x[3], y[3];
            ok = 1;

            for (int j = 0; j <= 2; j++) {
                x[j] = sum[i].t[j];
                y[j] = sum[poz].t[j];
            }
            for (int j = 0; j <= 2; j++)
                fprintf (g, "%d %d ", x[j], y[j]);
        }
    }

    if (!ok)
        fprintf (g, "-1\n");
}

int main() {
    read();
    precompute();
    solve();

    fclose(f);
    fclose(g);

    return 0;
}