Cod sursa(job #1468892)

Utilizator om6gaLungu Adrian om6ga Data 7 august 2015 11:12:02
Problema Loto Scor 5
Compilator c Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 100
#define SIZE 1000000

int N, S, i, j, k, small = 1 >> 31, large = -1;
int a[NMAX + 5], cnt, aux, aux1, aux2;
long long int sum[SIZE + 5];
char *ind1, *ind2;

int cmp(const void * a, const void * b)
{
   return ( ((*(long long int*)a)&0xffffffff) - ((*(long long int*)b)&0xffffffff) );
}

int srch(int val, int a, int b)
{
    int m;
    if (a == b)
        return ((sum[a]&0xffffffff) == val ? a : 0);
    else if (b - a == 1)
    {
         if ((sum[a]&0xffffffff) == val)      return a;
         else if ((sum[b]&0xffffffff) == val) return b;
         else                                 return 0;
    }
    else
    {
        m = (a+b)>>1;
        if ((sum[m]&0xffffffff) == val)       return m;
        else if ((sum[a]&0xffffffff) > val)   return srch(val, a, m-1);
        else                                  return srch(val, m+1, b);
    }   
}

int main()
{
    FILE *in, *out;
    in  = fopen("loto.in", "r");
    out = fopen("loto.out", "w");
    fscanf(in, "%d %d\n", &N, &S);
    
    for (i = 1; i <= N; i++)
    {
        fscanf(in, "%d", &a[i]);
        if (a[i] < small)
            small = a[i];
        else if (a[i] > large)
            large = a[i];
    }
        
    for (i = 1; i <= N; i++)
    for (j = 1; j <= N; j++)
    for (k = 1; k <= N; k++)
    {
        cnt++;
        sum[cnt] = ((i<<16) + (j<<8) + k);
        sum[cnt] <<= 32;
        sum[cnt] += (a[i] + a[j] + a[k]);
        aux = sum[cnt]>>32;
    }
    qsort(&sum[1], cnt, sizeof(long long int), cmp);
    
    aux = 1;
    for (i = 2; i <= cnt; i++)
        if ((sum[aux]&0xffffffff) < (sum[i]&0xffffffff))
            sum[++aux]= sum[i];
    cnt = aux;
    
    aux = 0;
    for (i = 1; i <= cnt && (sum[i]&0xffffffff) <= S/2; i++)
    {
        j = srch(S - (sum[i]&0xffffffff), i, cnt);
        if (j)
        {
            aux1 = sum[i]>>32;
            aux2 = sum[j]>>32;
            ind1 = (char*)&aux1;
            ind2 = (char*)&aux2;
            fprintf(out, "%d %d %d %d %d %d\n", a[ind1[2]], 
                                                a[ind1[1]], 
                                                a[ind1[0]], 
                                                a[ind2[2]], 
                                                a[ind2[1]], 
                                                a[ind2[0]]);
            aux++;
            break;
        }
    }
    
    if (!aux)
        fprintf(out, "-1\n");
    
    fclose(in);
    fclose(out);
    return 0;
}