Pagini recente » Cod sursa (job #694263) | Cod sursa (job #1064080) | Cod sursa (job #1632956) | Cod sursa (job #2453864) | Cod sursa (job #175073)
Cod sursa(job #175073)
#include<stdio.h>
#define INPUT "loto.in"
#define OUTPUT "loto.out"
#define NMAX 101
#define DMAX 1000001
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
int N;
long S, cont;
long nr[ NMAX ], value[ DMAX ], val[ DMAX ];
long left = 0, right;
int OK = 1, i, j, k;
long Cont;
void readValues()
{
fscanf(fin, "%d %ld", &N, &S);
for(i = 0; i < N; ++i)
fscanf(fin, "%ld", &nr[ i ]);
}
void setInitial()
{
cont = 0;
for(i = 0; i < N; ++i)
for(j = 0; j < N; ++j)
for(k = 0; k < N; ++k)
{
value[ cont ] = nr[ i ] + nr[ j ] + nr[ k ];
val[ cont ] = cont;
++cont;
}
}
void printSolution(long valor)
{
if(valor != -1)
{
Cont = 0;
while(valor >= N * N)
{
valor -= N * N;
++Cont;
}
fprintf(fout, "%ld ", nr[ Cont ]);
Cont = 0;
while(valor >= N)
{
valor -= N;
++Cont;
}
fprintf(fout, "%ld ", nr[ Cont ]);
fprintf(fout, "%ld ", nr[ valor ]);
}
else
fprintf(fout, "-1");
}
void binSearch()
{
right = cont;
while( left < right && OK)
{
while(value[ left ] + value[ right ] > S )
--right;
while(value[ left ] + value[ right ] < S )
++left;
if(value[ left ] + value[ right ] == S)
{
printSolution(val[ left ]);
printSolution(val[ right ]);
break;
}
}
if(left >= right)
printSolution(-1);
fprintf(fout, "\n");
}
void quickSort(long st, long dr)
{
long l = st, m = dr;
while( l != m)
{
if( ( l < m && value[ l ] > value[ m ]) || ( l > m && value[ l ] < value[ m ]))
{
value[ l ] = value[ l ] + value[ m ];
value[ m ] = value[ l ] - value[ m ];
value[ l ] = value[ l ] - value[ m ];
val[ l ] = val[ l ] + val[ m ];
val[ m ] = val[ l ] - val[ m ];
val[ l ] = val[ l ] - val[ m ];
l = l + m;
m = l - m;
l = 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);
}
int main()
{
readValues();
setInitial();
quickSort(0, cont);
binSearch();
fclose(fin);
fclose(fout);
return 0;
}