Cod sursa(job #1469081)

Utilizator om6gaLungu Adrian om6ga Data 7 august 2015 16:00:29
Problema Loto Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.61 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 (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]);
    qsort(&a[1], N, sizeof(int), cmp);
          
    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);
    
    i = 1;
    j = cnt;

    aux = 0;
    while (i <= j && sum[i].val <= S/2)
    {
        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--;
    }

    /*also works
    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;
}