Pagini recente » Cod sursa (job #2002708) | Cod sursa (job #581382) | Cod sursa (job #3197293) | Cod sursa (job #2647551) | Cod sursa (job #48322)
Cod sursa(job #48322)
#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);
}