Cod sursa(job #631985)

Utilizator sebii_cSebastian Claici sebii_c Data 9 noiembrie 2011 23:26:25
Problema Loto Scor 5
Compilator c Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <stdlib.h>
#define KMAX 101
#define NMAX 330000

struct nod {
    int s;
    int i, j, k;
};

struct nod A[NMAX];
int V[KMAX];

int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    int N, S, i, j, k;
    scanf("%d %d", &N, &S);
    int nr = 0;
    
    for (i=0; i<N; ++i) 
	scanf("%d", &V[i]);

    for (i=0; i<N; ++i)
	for (j=0; j<N; ++j)
	    for (k=0; k<N; ++k) {
		A[++nr].s = V[i] + V[j] + V[k];
		A[nr].i = V[i];
		A[nr].j = V[j];
		A[nr].k = V[k];
	    }
    
    qsort(A, nr+1, sizeof(int), compare);
    
    int hi, lo, mid, val, ok = 1;
    for (i=1; i<=nr && ok; ++i) {
	val = S - A[i].s;	
	hi = nr, lo = 1;
	ok = 1;
	while (lo <= hi && ok) {
	    mid = lo + (hi - lo)/2;
	    if (A[mid].s == val) {
		printf("%d %d %d %d %d %d\n", A[i].i, A[i].j, A[i].k, A[mid].i, A[mid].j, A[mid].k);
		ok = 0;
	    }
	    if (A[mid].s > val)
		hi = mid - 1;
	    if (A[mid].s < val)
		lo = mid + 1;
	}
    }
    
    if (ok)
	printf("-1\n");
    return 0;
}