Cod sursa(job #365231)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 noiembrie 2009 10:28:50
Problema Loto Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
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 cmp (numere x,numere y)
{
    return (x.a<y.a);
}
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;
            }
    sort(s+1,s+u+1,cmp);
    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;
}