Cod sursa(job #365237)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 noiembrie 2009 10:54:29
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include<stdio.h>
struct numere
{
    int a,b;
};
int i,u,v[105],s1,sum,s2,aux,n,j,t,st,dr,ok,m,maxi,l1,l2,l3;
numere s[5655005];
int partitionare (int st,int dr)
{
    int i,j,m;
    int pivot,aux;
    m=(st+dr)/2;
    pivot=s[m].a;
    i=st-1;
    j=dr+1;
    while(1)
    {
        do{++i;}while(s[i].a<pivot);
        do{--j;}while(s[j].a>pivot);
        if(i<j)
        {
            aux=s[i].a;
            s[i].a=s[j].a;
            s[j].a=aux;
            aux=s[i].b;
            s[i].b=s[j].b;
            s[j].b=aux;
            
        } //if
        else
	        return j;
    }//while
}//func

void quick(int st,int dr)
{
    int p;
    if(st<dr)
    {
        p=partitionare(st,dr);
        quick(st,p);
        quick(p+1,dr);
    }//if
}

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]);
        if(v[i]>maxi)
            maxi=v[i];
    }
    if(maxi*6<sum)
    {
        printf("-1");
        return 0;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(t=1;t<=n;t++)
            {
                s[++u].a=v[i]+v[j]+v[t];
                s[u].b=i*1000000+j*1000+t;
            }
            quick(1,u);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(t=1;t<=n;t++)
            {
                s2=v[i]+v[j]+v[t];s1=sum-s2;
                st=1;
                dr=u;ok=0;
                while(st<=dr)
                {
                    m=(st+dr)/2;
                    if(s1<s[m].a)
                        dr=m-1;
                    else
                        if(s1>s[m].a)
                            st=m+1;
                    else
                    {
                        ok=1;
                        break;
                    }
               }
               if(ok)
               {
                    l1=s[m].b/1000000;
                    l2=(s[m].b%1000000)/1000;
                    l3=s[m].b%1000;
                    printf("%d %d %d %d %d %d",v[i],v[j],v[t],v[l1],v[l2],v[l3]);
                    return 0;
               }
           } //for
    printf("-1");
    return 0;
}