Cod sursa(job #430)

Utilizator raula_sanChis Raoul raula_san Data 11 decembrie 2006 11:24:24
Problema Loto Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<cstdio>
#include<stdlib.h>
#define dim 101

using namespace std;

int N, S, K;
int A[dim];

struct TRIPLET {int a, b, c, s;} T[dim*dim*dim];

void read()
{
     freopen("loto.in", "r", stdin);
     scanf("%d %d", &N, &S);
     
     int i;
     for(i=1; i<=N; ++i)
              scanf("%d", A + i);
     fclose(stdin);
}

void process()
{
     int i, j, k;
     for(i=1; i<=N; ++i)
              for(j=1; j<=N; ++j)
                       for(k=1; k<=N; ++k)
                       {
                                ++ K;       
								T[K].a = A[i]; T[K].b = A[j]; T[K].c = A[k];
                                T[K].s = A[i] + A[j] + A[k];
                       }
}

int divide(int p, int q)
{
    int st = p, dr = q;
    TRIPLET x = T[st];
    
    while(st < dr)
    {
             while(st < dr && T[dr].s >= x.s) -- dr;
             T[st] = T[dr];
             while(st < dr && T[st].s <= x.s) ++ st;
             T[dr] = T[st];
    }
    T[st] = x;
    return st;
}

void qsort(int p, int q)
{
     int m = divide(p, q);
     
     if(m - 1 > p) qsort(p, m-1);
     if(m + 1 < q) qsort(m+1, q);
}

int cbin(int val)
{
    int ls = 1, ld = K, m;
    while(ls <= ld)
    {
             m = (ls + ld) / 2;
             if(T[m].s == val)
                       return m;
             else
             {
                 if(T[m].s < val) ls = m + 1;
                 if(T[m].s > val) ld = m - 1;
             }
    }
    return 0;
}

void write(int i, int j)
{
     freopen("loto.out", "w", stdout);
     printf("%d %d %d %d %d %d", T[i].a, T[i].b, T[i].c, T[j].a, T[j].b, T[j].c);
     fclose(stdout);
}

void choose()
{
     int i, poz;
     for(i=1; i<=K; ++i)
     {
              poz = cbin(S - T[i].s);
              if(poz)
              {
                     write(i, poz);
                     exit(0);
              }
     }
}

void print()
{
     freopen("loto.out", "w", stdout);
     printf("-1");
     fclose(stdout);
}

int main()
{
    read();
    process();
    qsort(1, K);
    choose();
    print();
    
    return 0;
}