Cod sursa(job #82824)

Utilizator risenshineAkil Nasser risenshine Data 9 septembrie 2007 13:29:45
Problema Loto Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100

int n, s, a[NMAX];
int value[NMAX*NMAX*NMAX], pos[NMAX*NMAX*NMAX], p[NMAX*NMAX*NMAX];

int comp(const void * a, const void * b) {
    return value[*(int*)a] - value[*(int*)b];
}
int bcomp(const void * a, const void * b) {
    return *(int*)a - value[*(int*)b];
}
int mybsearch(int key, int left, int right) {
    int m;
    while (left < right) {
        m = (left+right) / 2;
        if (key == value[p[m]])
            return m;
        else if (key < value[p[m]])
            right = m-1;
        else
            left = m+1;
    }
    return -1;
}
int main() {
    int i, j, k, l;
    int *q;
    int m;
    int key, temp;
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    scanf("%d %d", &n, &s);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (i = 0, temp = n*n*n; i < temp; i++)
        p[i] = i;
    for (i = l = 0; i < n; i++)
        for (j = 0; j < n; j++)
            for (k = 0; k < n; k++) {
                value[l] = a[i] + a[j] + a[k];
                pos[l] = i + j*100 + k*10000;
                l++;
            }
    qsort(p, l, sizeof(int), comp);
    for (i = 0; i < l; i++) {
        key = s - value[p[i]];
        if (key > 0) {
            /*q = (int*) bsearch(&key, p, l, sizeof(int), bcomp);
            if (q) {
                printf("%d %d %d ", a[pos[p[i]]%100], a[(pos[p[i]]/100) % 100], a[(pos[p[i]]/10000) % 100]);
                printf("%d %d %d\n", a[pos[*q]%100], a[(pos[*q]/100) % 100], a[(pos[*q]/10000) % 100]);
                return 0;
            }*/
            m = mybsearch(key, 0, l);
            if (m != -1) {
                printf("%d %d %d ", a[pos[p[i]]%100], a[(pos[p[i]]/100) % 100], a[(pos[p[i]]/10000) % 100]);
                printf("%d %d %d\n", a[pos[p[m]]%100], a[(pos[p[m]]/100) % 100], a[(pos[p[m]]/10000) % 100]);
                return 0;
            }
        }
    }
    printf("-1\n");
    return 0;
}