Cod sursa(job #642454)

Utilizator portocalaDiculescu Elena Alexandra portocala Data 1 decembrie 2011 13:48:22
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include "stdio.h"
#define dim 1000004
long long V[102], Sums[dim], limit, sol[7], keys[dim];

int count = 0,N;

long long genSums() {
  long 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*1000000 + j*1000 + k;
      }
    }
  }
  return c;
}

long long find(long long value) {
  long 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(long long *W, int li, int ls) {
  int i = li, j = ls, p = (i + j) / 2;
  long 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;
  long 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] % 1000; keys[a] /= 1000;
      sol[2] = keys[a] % 1000; keys[a] /= 1000;
      sol[3] = keys[a];
      sol[4] = keys[b] % 1000; keys[b] /= 1000;
      sol[5] = keys[b] % 1000; keys[b] /= 1000;
      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;
}