Cod sursa(job #1145144)

Utilizator gapdanPopescu George gapdan Data 17 martie 2014 21:52:32
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,s,nr;
struct camp
{
    int sum,x,y,z;
}v[1000005];
int cautbin(int val)
{
    int i, step;
    for (step=1;step<nr;step<<=1);
    for (i=0;step;step>>=1)
        if (i+step<nr && v[i+step].sum<=val)
           i+=step;
    return i;
}
int cmp(camp r,camp q)
{
    if (r.sum>q.sum) return 0;
    return 1;
}
int main()
{
    int a[101],i,j,k;
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&s);
    for (i=1;i<=n;++i)
        scanf("%d",&a[i]);
    nr=0;
    for (i=1;i<=n;++i)
        for (j=i;j<=n;++j)
            for(k=j;k<=n;++k)
            {
                ++nr;
                v[nr].sum=a[i]+a[j]+a[k];
                v[nr].x=a[i];
                v[nr].y=a[j];
                v[nr].z=a[k];
            }
    sort(v+1,v+nr+1,cmp);
    int e=0;
    for (i=1;i<nr;++i)
    {
        if (s-v[i].sum!=0)
       {
            int poz=cautbin(s-v[i].sum);
            if (poz!=-1)
            {
                printf("%d %d %d %d %d %d",v[i].x,v[i].y,v[i].z,v[poz].x,v[poz].y,v[poz].z);
                e=1;
                break;
            }
       }
    }
    if (e==0) printf("-1");
    return 0;
}