Cod sursa(job #487218)

Utilizator stephy_yoyoIonescu Stefania stephy_yoyo Data 24 septembrie 2010 13:23:09
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
# include <cstdio>
# include <algorithm>
 
using namespace std;
 
struct suma
{
    long long s;
    int a,b,c;
};
 
suma su[1000000];
long long val[101],S;
int N,i,j,k,poz=0,v[6];
 
int cmp (suma x,suma y)
{
    return (x.s<y.s);
}
 
int cautbin (long long x)
{
    int min=1,max=poz;
    while (min<=max)
    {
        if (x==su[(min+max)/2].s)
            return (min+max)/2;
        else
            if (x<su[(min+max)/2].s)
                max=(min+max)/2-1;
            else
                min=( min+max)/2+1;
    }
    return 0;
}
 
int main ()
{
    freopen ("loto.in","r",stdin);
    freopen ("loto.out","w",stdout);
    scanf ("%d%lld",&N,&S);
    for (i=1;i<=N;i++)
        scanf ("%lld",&val[i]);
    for (i=1;i<=N;i++)
        for(j=i;j<=N;j++)
            for (k=j;k<=N;k++)
           {
                su[++poz].s=val[i]+val[j]+val[k];
                su[poz].a=val[i];
                su[poz].b=val[j];
                su[poz].c=val[k];
            }
   sort(su+1,su+poz+1,cmp);
   for (i=1;i<=poz;i++)
       if(k=cautbin(S-su[i].s))
        {
            v[0]=su[i].a;
           v[1]=su[i].b;
            v[2]=su[i].c;
           v[3]=su[k].a;
            v[4]=su[k].b;
           v[5]=su[k].c;
            sort(v,v+6);
            for (j=0;j<=5;j++)
                printf ("%d ",v[j]);
            return 0;
        }
    printf ("-1");
    return 0;
}