Cod sursa(job #271604)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 5 martie 2009 16:54:51
Problema Loto Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
using namespace std;
int v[100],sum[1000010],i,k,poz,S,j,l,x,poz1,poz2,n,ok,p;
struct sir {int x,y,z;} a[1000010],aux;

int binar(int val)
{   
    int i, step;   
    for (step = 1; step < k; step <<= 1);
    for (i = 0; step; step >>= 1)   
        if (i + step < k && sum[i + step] <= val)
           i += step;   
    return i;   
}

int pozitie(int i, int j)
{
int di=1,dj=0,aux2;
while(i<j)
 { if(sum[i]>sum[j]) { aux2=sum[i]; sum[i]=sum[j]; sum[j]=aux2;
                       aux=a[i]; a[i]=a[j]; a[j]=aux;
                       aux2=di; di=dj; dj=aux2;
                     }
   i+=di;
   j-=dj;
 }
return i;
}
void quick(int s, int d)
 { if(s<d)
    {int p=pozitie(s,d);
      quick(s,p-1);
      quick(p+1,d);
    }
 }
int main()
{
FILE *f=fopen("loto.in","r");
FILE *g=fopen("loto.out","w");
fscanf(f,"%d %d",&n,&S);

for(i=1;i<=n;i++) fscanf(f,"%d",&v[i]);

for(i=1;i<=n;i++)
 for(j=i;j<=n;j++)
  for(l=j;l<=n;l++)
    { sum[++k]=v[i]+v[j]+v[l];
      a[k].x=v[i]; a[k].y=v[j]; a[k].z=v[l];
    }
quick(1,k);

for(i=1;i<=k;i++)
 { x=S-sum[i];

   p=binar(x);

   if(sum[p]==x) {ok=1; poz1=i; poz2=p; break;}
  }
if(!ok) fprintf(g,"%s","-1");
else fprintf(g,"%d %d %d %d %d %d",a[poz1].x,a[poz1].y,a[poz1].z,a[poz2].x,a[poz2].y,a[poz2].z);
fclose(f);
fclose(g);
return 0;
}