Cod sursa(job #153681)

Utilizator CezarMocanCezar Mocan CezarMocan Data 10 martie 2008 18:02:49
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct loto {long x; long p1; long p2; long p3;};

loto x[1000010];
long nrx,i,j,k,n,s,g,sum,aux,poz1,poz2;
long v[1310];

bool cmp(loto a, loto b)
    {
    if (a.x<b.x)    
        return true;
    else
        return false;
    }
    
long gasit(long n, long ls, long ld)
    {
    long m=(ls+ld)/2;
    if (x[m].x==n)
        return m;
    if (ls>=ld)
        return 0;
    if (n<x[m].x)
        return gasit(n,ls,m-1);
    else
        return gasit(n,m+1,ld);
    }

int main(){
freopen("loto.in","r",stdin);
freopen("loto.out","w",stdout);
scanf("%d%d",&n,&s);
for (i=1;i<=n;i++)
    scanf("%d",&v[i]);
sort(v+1,v+n+1);
for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
        for (k=1;k<=n;k++)
            {
            nrx++;
            x[nrx].x=v[i]+v[j]+v[k];
            x[nrx].p1=i;
            x[nrx].p2=j;
            x[nrx].p3=k;   
            }
sort(x+1,x+nrx+1,cmp);
for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
        for (k=1;k<=n;k++)
            {
            sum=s-(v[i]+v[j]+v[k]);
            g=gasit(sum,1,nrx);
            if ((sum>=0)&&(g))    
                {
                printf("%d %d %d %d %d %d \n",v[i],v[j],v[k],v[x[g].p1],v[x[g].p2],v[x[g].p3]);
                return 0;
                }
            }
printf("-1\n");
return 0;
}