Cod sursa(job #1469018)

Utilizator om6gaLungu Adrian om6ga Data 7 august 2015 15:15:31
Problema Loto Scor 65
Compilator c Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <stdio.h>
#include <stdlib.h>
  
#define NMAX 100
#define SIZE 1000000
  
typedef struct {
    int val;
    char ind1, ind2, ind3;
} myint;
  
int N, S, i, j, k, small = 1 >> 31, large = -1;
int a[NMAX + 5], cnt, aux;
myint sum[SIZE + 5];
  
int cmp(const void * a, const void * b)
{
   return ( (*(int*)a) - (*(int*)b) );
}
  
int srch(int val, int a, int b)
{
    int m;
    if (a == b)
        return (sum[a].val == val ? a : 0);
    else if (b - a == 1)
    {
         if (sum[a].val == val)
             return a;
         else if (sum[b].val == val)
             return b;
         else
             return 0;
    }
    else
    {
        m = (a+b)>>1;
        if (sum[m].val == val)
            return m;
        else if (sum[m].val > 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 = i; j <= N; j++)
    for (k = j; k <= N; k++)
    {
        sum[++cnt].val = a[i] + a[j] + a[k];
        sum[cnt].ind1 = i;
        sum[cnt].ind2 = j;
        sum[cnt].ind3 = k;
    }
    qsort(&sum[1], cnt, sizeof(myint), cmp);
      
    aux = 1;
    for (i = 2; i <= cnt; i++)
        if (sum[aux].val < sum[i].val)
        {
            sum[++aux].val = sum[i].val;
            sum[aux].ind1 = sum[i].ind1;
            sum[aux].ind2 = sum[i].ind2;
            sum[aux].ind3 = sum[i].ind3;
        }
    cnt = aux;
    
    i = 1;
    j = cnt;

    while (i < j)
    {
        if (sum[i].val + sum[j].val == S)
        {
            fprintf(out, "%d %d %d %d %d %d\n", a[sum[i].ind1],
                                                a[sum[i].ind2],
                                                a[sum[i].ind3],
                                                a[sum[j].ind1],
                                                a[sum[j].ind2],
                                                a[sum[j].ind3]);
            aux++;
            break;
        }
        else if (sum[i].val + sum[j].val < S)
            i++;
        else
        {
            j--;
            if (i >= 2)
                i--;
        }
    }

    /*aux = 0;
    for (i = 1; i <= cnt && sum[i].val <= S/2; i++)
    {
        j = srch(S - sum[i].val, i, cnt);
        if (j)
        {
            fprintf(out, "%d %d %d %d %d %d\n", a[sum[i].ind1],
                                                a[sum[i].ind2],
                                                a[sum[i].ind3],
                                                a[sum[j].ind1],
                                                a[sum[j].ind2],
                                                a[sum[j].ind3]);
            aux++;
            break;
        }
    }*/
      
    if (!aux)
        fprintf(out, "-1\n");
      
    fclose(in);
    fclose(out);
    return 0;
}