Cod sursa(job #611966)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 5 septembrie 2011 10:33:02
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>
#define N 1000001
long n,i,j,k,m,s,v[101],y[101],t,x[7],nr,r[N],c[N],d[N],e[N],ok,a,b;

void merge(long v[101],int p,int q)
{int m=(p+q)/2,i,j,k;
if(p==q)
      return;
merge(v,p,m);
merge(v,m+1,q);
for(i=p,j=m+1,k=p;i<=m||j<=q;)
if(j>q||(i<=m&&v[i]<v[j]))
      y[k++]=v[i++];
else
      y[k++]=v[j++];
for(i=p;i<=q;i++)
      v[i]=y[i];}

int main()
{freopen("loto.in","r",stdin);
freopen("loto.out","w",stdout);
scanf("%ld%ld",&n,&s);
for(i=1;i<=n;i++)
     scanf("%ld",&v[i]);
merge(v,1,n);
t=s;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
     {r[++nr]=v[i]+v[j]+v[k];
     c[nr]=v[i],d[nr]=v[j],e[nr]=v[k];}
for(i=1;i<=nr&&!ok;i++)
     {s=t-r[i];
     a=1,b=nr;
     while(a<=b&&!ok)
           {m=(a+b)/2;
           if(s==r[m])
                   {x[1]=c[i],x[2]=d[i],x[3]=e[i],x[4]=c[m],x[5]=d[m],x[6]=e[m];
                   merge(x,1,6);
                   ok=1;}
           if(r[m]>s)
                   b=m-1;
           if(r[m]<s)
                   a=m+1;}}
if(!ok)
     printf("-1");
else
     printf("%ld %ld %ld %ld %ld %ld",x[1],x[2],x[3],x[4],x[5],x[6]);
return 0;}