Cod sursa(job #491665)

Utilizator chrissBota Cristian chriss Data 11 octombrie 2010 22:18:51
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>

int v[101],n,sum,i,j,k,st,dr,find,i2,i3,mij,t;
struct loto{char a,b,c;
            int s;};
loto a[1000010],aux;

void interschimba(loto &x, loto &y)
{
    aux=x;
    x=y;
    y=aux;
}
void qsort(int l, int r)
{
    int st=l,dr=r;
    int pivot=a[(l+r)/2].s;
    while(st<=dr)
    {
        while(a[st].s < pivot) ++st;
        while(a[dr].s > pivot) --dr;
        if(st<=dr)
        {
            interschimba(a[st],a[dr]);
            ++st;
            --dr;
        }
    }
    if(l<dr) qsort(l,dr);
    if(st<r) qsort(st,r);
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    scanf("%d %d",&n,&sum);
    for(i=1; i<=n; ++i)
        scanf("%d",&v[i]);
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            for(k=1; k<=n; ++k)
            {
                t++;
                a[t].a=i;
                a[t].b=j;
                a[t].c=k;
                a[t].s=v[i]+v[j]+v[k];
            }
    qsort(1,t);

    for(i=1; (i<=t) && (a[i].s <= sum-a[1].s); ++i)
    {
        find=sum-a[i].s;
        st=1;
        dr=t;
        if(a[i].s!=a[i-1].s)
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(a[mij].s==find)
                {
                    i2=i;
                    i3=mij;
                    i+=t;
                    st=dr+1;
                }
                if(a[mij].s<find) st=mij+1;
                if(a[mij].s>find) dr=mij-1;
            }
    }
    if(i2!=0)
        printf("%d %d %d %d %d %d",v[a[i2].a],v[a[i2].b],v[a[i2].c],v[a[i3].a],v[a[i3].b],v[a[i3].c]);
    else
        printf("-1");
    return 0;
}