Pagini recente » Cod sursa (job #3271671) | Cod sursa (job #557310) | Cod sursa (job #3259615) | Cod sursa (job #641919)
Cod sursa(job #641919)
#include "stdio.h"
#define dim 1000004
unsigned long V[102], Sums[dim], limit, sol[7];
int count = 0,N,keys[dim];
unsigned long genSums() {
long c = 0;
for(int i = 1; i <= N; i++) {
for(int j = i; j <= N; j++) {
for(int k = j; k <= N; k++) {
Sums[++c] = V[i] + V[j] + V[k];
keys[c] = i*100 + j*10 + k;
}
}
}
return c;
}
unsigned long find(unsigned long value) {
unsigned long li = 1, ls = limit, poz = (ls-li) / 2 + li;
while (li < poz && poz < ls) {
if(Sums[poz] == value)
return poz;
if(Sums[poz] < value){
li = poz;
poz = (ls - li) / 2 + li;
}
else {
ls = poz;
poz = (ls - li) / 2 + li;
}
}
return poz;
}
void quickSort(unsigned long *W, int li, int ls) {
int i = li, j = ls, p = (i + j) / 2;
unsigned long aux;
while (i <= j) {
while (W[i] < W[p])
i++;
while (W[j] > W[p])
j--;
if(i <= j) {
aux = W[i];
W[i] = W[j];
W[j] = aux;
aux = keys[i];
keys[i] = keys[j];
keys[j] = aux;
i++;
j--;
}
}
if (li < j)
quickSort(W, li, j);
if (i < ls)
quickSort(W, i, ls);
}
int main() {
freopen("loto.in","r",stdin);
freopen("loto.out","w",stdout);
int i;
unsigned long S, a, b;
scanf("%d %ld",&N, &S);
for (i = 1; i <= N; i++) {
scanf("%ld", &V[i]);
}
// quickSort(V, 1, N);
limit = genSums();
quickSort(Sums, 1, limit);
a = find(S);
b = find(S-Sums[a]);
while((Sums[a] + Sums[b]) >= S) {
if ((Sums[a] + Sums[b]) == S) {
sol[1] = keys[a] % 10; keys[a] /= 10;
sol[2] = keys[a] % 10; keys[a] /= 10;
sol[3] = keys[a];
sol[4] = keys[b] % 10; keys[b] /= 10;
sol[5] = keys[b] % 10; keys[b] /= 10;
sol[6] = keys[b];
quickSort(sol, 1, 6);
for(i = 1; i < 7; i++) {
printf("%ld ", V[sol[i]]);
}
printf("\n");
break;
}
else {
a = find(Sums[a]-1);
b = find(S-Sums[a]);
}
}
if ((Sums[a] + Sums[b]) != S)
printf("-1\n");
return 0;
}