Cod sursa(job #179763)

Utilizator AlxCojocaru Alexandru Alx Data 16 aprilie 2008 12:26:39
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <stdio.h>
int n,s,a[100],nr=0;
struct element
{
    int a,b,c,s;
};
element sum[1000000];
void schimba(int p, int q)
       {
    element aux=sum[p];
    sum[p]=sum[q];
    sum[q]=aux;
       }


int pivot(int p, int q)
    {
    while(p<q)
        {
        while(sum[p].s<=sum[q].s && p!=q)
         p++;
        if(p<q) schimba(p,q);
        while(sum[p].s<=sum[q].s && p!=q)
         q--;
        if(p<q)  schimba(p, q);
        }
    return p;
    }

void qsort(int p, int q)
    {
    if(q>p)
        {
        int k=pivot(p, q);
        qsort(p, k-1);
        qsort(k+1, q);
        }
    }
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++)
    {
        int step,val=s-sum[i].s;
        for (step = 1; step < nr; step <<= 1);
        for (j = 0; step; step >>= 1)
            if (j + step < nr && sum[j + step].s <= val)
                j += step;
        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;
}