Cod sursa(job #804447)

Utilizator savimSerban Andrei Stan savim Data 29 octombrie 2012 20:11:34
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

const int MAX_N = 105;

int n, s, k;

int A[MAX_N];

struct element {
    int S, x, y;
} V[MAX_N * MAX_N * MAX_N];

inline int cmp(const element &P, const element &Q) {
    return P.S < Q.S;
}

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", &A[i]);

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            for (int t = j; t <= n; t++) {
                V[++k].S = A[i] + A[j] + A[t];
                V[k].x = A[i];
                V[k].y = A[j];
            }

    sort(V + 1, V + k + 1, cmp);

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            for (int t = j; t <= n; t++) {
                int rem = s - A[i] - A[j] - A[t];

                int st = 0, dr = k + 1, mid = 0;
                while (st + 1 < dr) {
                    mid = (st + dr) / 2;
                    if (V[mid].S > rem)
                        dr = mid;
                    if (V[mid].S < rem)
                        st = mid;
                    if (V[mid].S == rem) {
                        printf("%d %d %d %d %d %d\n", A[i], A[j], A[t], V[mid].x, V[mid].y, V[mid].S - V[mid].x - V[mid].y);
                        return 0;
                    }
                }
            }
    printf("-1\n");

    return 0;
}