Cod sursa(job #1143962)

Utilizator cbanu96Banu Cristian cbanu96 Data 16 martie 2014 13:37:27
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define FILEIN "loto.in"
#define FILEOUT "loto.out"
#define NMAX 101

int N, V[NMAX], S;

struct Half {
    int Value;
    int Nr[3];
};

Half Sums[NMAX*NMAX*NMAX];

inline bool SumCompare(const Half& A, const Half& B) {
    return A.Value < B.Value;
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &N, &S);
    for ( int i = 1; i <= N; i++ ) {
        scanf("%d", &V[i]);
    }

    int SumCounter = 0;
    for ( int i = 1; i <= N; i++ ) {
        for ( int j = 1; j <= N; j++ ) {
            for ( int k = 1; k <= N; k++ ) {
                ++SumCounter;
                Sums[SumCounter].Value = V[i]+V[j]+V[k];
                Sums[SumCounter].Nr[0] = V[i], Sums[SumCounter].Nr[1] = V[j], Sums[SumCounter].Nr[2] = V[k];
            }
        }
    }

    sort(Sums+1, Sums+SumCounter+1, SumCompare);

    for ( int i = 1; i <= SumCounter; i++ ) {
        int l, r, mid;
        l = 1, r = SumCounter;
        int val = S - Sums[i].Value;
        while (l < r) {
            mid = (l+r)/2;
            if (Sums[mid].Value < val) {
                l = mid+1;
            } else {
                r = mid-1;
            }
        }
        if (Sums[mid].Value == val ) {
            printf("%d %d %d %d %d %d\n", Sums[i].Nr[0], Sums[i].Nr[1], Sums[i].Nr[2], Sums[mid].Nr[0], Sums[mid].Nr[1], Sums[mid].Nr[2]);
            return 0;
        }
    }

    printf("-1\n");


    return 0;
}