Cod sursa(job #529133)

Utilizator ioanabIoana Bica ioanab Data 4 februarie 2011 13:06:26
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
# include <cstdio>
# include <algorithm>
 
using namespace std;
 
struct suma
{
    long long s;
    int a,b,c;
};
 
suma sum[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==sum[(min+max)/2].s)
            return (min+max)/2;
        else
            if (x<sum[(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++)
           {
                sum[++poz].s=val[i]+val[j]+val[k];
                sum[poz].a=val[i];
                sum[poz].b=val[j];
                sum[poz].c=val[k];
            }
   sort(sum+1,sum+poz+1,cmp);
   for (i=1;i<=poz;i++)
       if(k=cautbin(S-sum[i].s))
        {
            v[0]=sum[i].a;
           v[1]=sum[i].b;
            v[2]=sum[i].c;
           v[3]=sum[k].a;
            v[4]=sum[k].b;
           v[5]=sum[k].c;
            sort(v,v+6);
            for (j=0;j<=5;j++)
                printf ("%d ",v[j]);
            return 0;
        }
    printf ("-1");
    return 0;
}