Cod sursa(job #641917)

Utilizator portocalaDiculescu Elena Alexandra portocala Data 29 noiembrie 2011 22:06:56
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#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;
}