Cod sursa(job #238445)

Utilizator DraStiKDragos Oprica DraStiK Data 2 ianuarie 2009 10:42:58
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include<stdlib.h>
struct triplu
{
    int a,b,c,sm;
};
int n,s,u;
int a[105];
triplu t[105*105*105];
void read ()
{
    int i;
    scanf ("%d%d",&n,&s);   
    for (i=1; i<=n; ++i)
        scanf ("%d",&a[i]); 
    fclose(stdin);
}
void solve ()
{
    int i,j,k;
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            for (k=1; k<=n; ++k)
            {
                t[++u].a=a[i];
                t[u].b=a[j];
                t[u].c=a[k];
                t[u].sm=a[i]+a[j]+a[k];
            }
}
int divide(int p, int q)
{
    int st=p,dr=q;
    triplu x=t[st];
    
    while(st<dr)
    {
             while(st<dr && t[dr].sm>=x.sm) 
                --dr;
             t[st]=t[dr];
             while(st<dr && t[st].sm<=x.sm) 
                ++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 in,sf,m;
    in=1;
    sf=u;
    while (in<=sf)
    {
        m=(in+sf)>>1;
        if (t[m].sm==val)
            return m;
        else
        {
            if(t[m].sm<val) 
                in=m+1;
            if(t[m].sm>val) 
                sf=m-1;
        }
    }
    return 0;
}
void print (int i,int j)
{
    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 solve_2 ()
{
    int i,poz;
    for (i=1; i<=u; ++i)
    {
        poz=cbin (s-t[i].sm);
        if (poz)
        {
            print (i,poz);
            exit (0);
        }
    }
}
int main ()
{
    freopen ("loto.in","r",stdin);
    freopen ("loto.out","w",stdout);
    read ();
    solve ();
    qsort (1,u);
    solve_2 ();
    printf ("-1");
    return 0;
}