Pagini recente » Cod sursa (job #690795) | Cod sursa (job #343953) | Cod sursa (job #351883) | Cod sursa (job #2264877) | Cod sursa (job #174355)
Cod sursa(job #174355)
#include<stdio.h>
#define INPUT "loto.in"
#define OUTPUT "loto.out"
#define NMAX 1000001
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
int N;
long S, a[ NMAX ], sum[ NMAX ];
void readValues()
{
fscanf(fin, "%d %ld", &N, &S);
for(int i = 1; i <= N; ++i)
fscanf(fin, "%ld", &a[ i ]);
}
void setInitial()
{
long cont = 1;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
for(int k = 1; k <= N; ++k)
{
sum[ cont++ ] = a[ i ] + a[ j ] + a[ k ];
/* sum[ cont ][ 1 ] = a[ i ];
sum[ cont ][ 2 ] = a[ j ];
sum[ cont++ ][ 3 ] = a[ k ];*/
}
}
inline void exchange(long& val1, long& val2)
{
val1 = val1 + val2;
val2 = val1 - val2;
val1 = val1 - val2;
}
void quickSort(long st, long dr)
{
long l = st, m = dr;
while( l != m)
{
if( ( l < m && sum[ l ] > sum[ m ]) || ( l > m && sum[ l ] < sum[ m ] ) )
{
exchange( sum[ l ], sum[ m ]);
/* exchange( sum[ l ][ 1 ], sum[ m ][ 1 ]);
exchange( sum[ l ][ 2 ], sum[ m ][ 2 ]);
exchange( sum[ l ][ 3 ], sum[ m ][ 3 ]);*/
exchange( l, m);
if(l < m)
--m;
else
++m;
}
else
if(l < m)
--m;
else
++m;
}
if(l != st) quickSort( st, l - 1);
if(l != dr) quickSort( l + 1, dr);
}
void printSolution(int code, long fValue, long sValue)
{
int cont;
if(code == 1)
{
cont = 1;
while(fValue > N * N)
{
fValue -= N * N;
++cont;
}
fprintf(fout, "%ld ", a[ cont ]);
cont = 1;
while(fValue > N )
{
fValue -= N;
++cont;
}
fprintf(fout, "%ld ", a[ cont ]);
fprintf(fout, "%ld ", a[fValue ]);
cont = 1;
while(sValue > N * N)
{
sValue -= N * N;
++cont;
}
fprintf(fout, "%ld ", a[ cont ]);
cont = 1;
while(sValue > N )
{
sValue -= N;
++cont;
}
fprintf(fout, "%ld ", a[ cont ]);
fprintf(fout, "%ld ", a[ sValue ]);
}
else
fprintf(fout, "-1\n");
}
void binSearch()
{
int Valid = 1;
long st = 1, dr = N * N * N;
while( st < dr && Valid)
{
if(sum[ st ] + sum[ dr ] == S)
{
printSolution(1, st, dr);
return;
}
while(sum[ st ] + sum[ dr ] > S)
--dr;
while(sum[ st ] + sum[ dr ] < S)
++st;
}
printSolution(-1,0,0);
}
int main()
{
readValues();
setInitial();
quickSort(1, N * N * N);
binSearch();
fclose(fin);
fclose(fout);
return 0;
}