Cod sursa(job #48322)

Utilizator mika17Mihai Alex Ionescu mika17 Data 4 aprilie 2007 17:46:48
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#include <time.h>
#define fin "loto.in"
#define fout "loto.out"
#define NMAX 100

int N,S,A[NMAX],sum[NMAX*NMAX*NMAX],ncube;
FILE * f = fopen(fin,"r") , * g = fopen(fout,"w");

void read_data();
void qsort(int[],int,int);
void solve();
void proc();

int main()
{
 read_data();
 proc();
 qsort(sum,0,ncube-1);
 solve();
return 0;
}

void read_data()
{
 fscanf(f,"%d %d",&N,&S);
 for(int i=0;i<N;++i)
   fscanf(f,"%d",&A[i]);
 ncube = N*N*N;
 fclose(f);
}

void proc()
{
 for(int i=0;i<N;++i)
    for(int j=0;j<N;++j)
       for(int k=0;k<N;++k)
	  sum[i*N*N+j*N+k] = A[i]+A[j]+A[k];
}

void qsort(int a[],int st,int dr) {
int i=st,j=dr,x=a[(st+dr)/2];
while(i<j)
{
 while(a[i]<x) ++i;
 while(a[j]>x) --j;
 if(i<=j)
   {
    int y=a[i]; a[i] = a[j]; a[j] = y;
    ++i; --j;
   }
}
if(i<dr) qsort(a,i,dr);
if(st<j) qsort(a,st,j);
}

int bsrc(int x)
{
 int step = 1 , pos=0;
 while(step*2<ncube) step<<=1;
 for(;step;step>>=1)
    if(pos+step<ncube & sum[pos+step]<=x)
      pos+=step;
 return pos;
}

void solve()               //O(N^3log(N^3))
{
 for(int i=0;i<N;++i)
  for(int j=0;j<N;++j)
   for(int k=0,pos;k<N;++k)
      if(A[i] + A[j] + A[k] + sum[ (pos = bsrc(S-A[i]-A[j]-A[k])) ] == S)
      {
       qsort(A,0,N-1);         //cautam numerele finale
       for(int l=0;l<N;++l)
	  for(int m=0;m<N;++m)
	     for(int n=0;n<N;++n)
	      if(A[l]+A[m]+A[n]==sum[pos])
	      {
	       fprintf(g,"%d %d %d %d %d %d",A[i],A[j],A[k],A[l],A[m],A[n]);
	       fclose(g);
	       return;
	      }
      }
 fprintf(g,"-1");
 fclose(g);
}