Cod sursa(job #855179)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 14 ianuarie 2013 19:02:35
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<algorithm>
#include<stdio.h>
using namespace std;
#define N_MAX 102
 
struct p
{
    int i,j,k,s;
    p()
    {
    }
    p(const int i,const int j,const int k,const int s)
    {
        this->i=i;
        this->j=j;
        this->k=k;
        this->s=s;
    }
    bool operator < (const p &other) const
    {
        return this->s<other.s;
    }
};
 
p a3[N_MAX*N_MAX*N_MAX];
 
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
 
    int a[N_MAX],n,i,j,k,S,s1,s2,s3,s,Len=0;
 
    scanf("%d%d",&n,&S);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
 
    for(i=1;i<=n;i++)
    {
        s1=a[i];
        for(j=1;j<=n;j++)
        {
            s2=s1+a[j];
            for(k=1;k<=n;k++)
            {
                s3=s2+a[k];
                if(s3>S)
                    continue;
                a3[++Len]=p(a[i],a[j],a[k],s3);
            }
        }
    }
     
    sort(a3+1,a3+Len+1);
 
    int lg,step,cb;
    for(lg=1;lg<Len;(lg<<=1));
 
    for(i=1;i<=Len;i++)
    {
        s=S-a3[i].s;
        for(step=lg,cb=0;step;(step>>=1))
        {
            if(cb+step<=Len&&a3[cb+step].s<=s)
                cb+=step;
        }
        if(a3[cb].s==s)
        {
            printf("%d %d %d %d %d %d\n",a3[i].i,a3[i].j,a3[i].k,a3[cb].i,a3[cb].j,a3[cb].k);
 
            return 0;
        }
    }
     
    printf("-1\n");
 
    return 0;
}