Cod sursa(job #179283)

Utilizator AlxCojocaru Alexandru Alx Data 15 aprilie 2008 19:35:33
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>
int n,s,a[100],nr=0;
struct element
{
    int a,b,c,s;
};
element sum[1000000];
void qsort(int li,int ls)
{
    if (ls-li>1)
    {
        int i=li,j=ls,i1=0,j1=-1;
        while (i<j)
        {
            if (sum[i].s>sum[j].s)
            {
                element aux=sum[i];
                sum[i]=sum[j];
                sum[j]=aux;
                int a2=i1;
                i1=-j1;
                j1=-a2;
            }
            i+=i1;
            j+=j1;
        }
        qsort(li,i);
        qsort(i+1,ls);
    }
}
int binary_search(int val)
{
    int i, step;
    for (step = 1; step < nr; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < nr && sum[i + step].s <= val)
           i += step;
    return i;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d %d\n",&n,&s);
    int i,j,k;
    for (i=0;i<n;i++)
        scanf("%d ",&a[i]);
    for (i=0;i<n;i++)
        for (j=i;j<n;j++)
            for (k=j;k<n;k++)
            if (a[i]+a[j]+a[k]<=s)
            {
                    sum[nr].a=a[i];
                    sum[nr].b=a[j];
                    sum[nr].c=a[k];
                    sum[nr].s=a[i]+a[j]+a[k];
                    nr++;
            }
    qsort(0,nr-1);
    int ok=0;
    for (i=0;i<=nr&&!ok&&sum[i].s<=s/2;i++)
    {
        j=binary_search(s-sum[i].s);
        if (sum[j].s==s-sum[i].s)
        {
            ok=1;
            printf("%d %d %d %d %d %d\n",sum[i].a,sum[i].b,sum[i].c,sum[j].a,sum[j].b,sum[j].c);
        }
    }
    if (!ok)
        printf("-1\n");
    return 0;
}