Cod sursa(job #1022869)

Utilizator NCodeMihai X NCode Data 6 noiembrie 2013 01:54:51
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <stdlib.h>
#include <iostream>
#include <fstream>

using namespace std;

struct sum3 {
  int a, b, c;
  int sum;
};


inline int CCompSum3(const void *p1, const void *p2) {
  int s1 = (*(sum3 *)p1).sum;
  int s2 = (*(sum3 *)p2).sum;
  return s1 == s2 ? 0 : (s1 < s2 ? -1 : 1);
}

const sum3 *Search(const sum3 *p_st, const sum3 *p_dr, int val) {
  if (p_st > p_dr) {
    return NULL;
  }

  const sum3 *p_mid = p_st + (p_dr - p_st) / 2;

  if (p_mid->sum == val) {
    return p_mid;
  }
  if (val < p_mid->sum) {
    return Search(p_st, p_mid - 1, val);
  }
  return Search(p_mid + 1, p_dr, val);
}


int main() {
  int s;
  unsigned n;
  int *numbers, *numbers_end;
  int *p_i, *p_j, *p_k;
  sum3 *sum, *sum_end;
  sum3 *p_sum;
  int sum_length;
  

  ifstream in("loto.in");
  in >> n >> s;
  numbers = (int *) malloc(n * sizeof(int));
  numbers_end = numbers + n;

  for (p_i = numbers; p_i < numbers_end; ++p_i) {
    in >> (*p_i);
  }
  in.close();

  sum_length = (n * (n + 1) * (n + 2)) / 6;
  sum = (sum3 *) malloc(sum_length * sizeof(sum3));
  sum_end = sum + sum_length;
  
  p_sum = sum;
  for (p_i = numbers; p_i < numbers_end; ++p_i) {
    register int a;
    a = *p_i;
    for (p_j = p_i; p_j < numbers_end; ++p_j) {
      register int b = *p_j;
      for (p_k = p_j; p_k < numbers_end; ++p_k) {
        register int c = *p_k;
        *(p_sum++) = {a, b, c, a + b + c};
      }
    }
  }

  qsort(sum, sum_length, sizeof(sum3), CCompSum3);

  const sum3 *p_sum_find;
  ofstream out("loto.out");
  for (p_sum = sum; p_sum < sum_end; ++p_sum) {
    if (p_sum->sum + p_sum->sum == s) {
      out << p_sum->a << " " << p_sum->b << " " << p_sum->c << " " <<
        p_sum->a << " " << p_sum->b << " " << p_sum->c;
      out.close();
      return 0;
    }

    p_sum_find = Search(p_sum + 1, sum_end - 1, s - p_sum->sum);
    if (p_sum_find != NULL) {
      out << p_sum->a << " " << p_sum->b << " " << p_sum->c << " " <<
        p_sum_find->a << " " << p_sum_find->b << " " << p_sum_find->c;
      out.close();
      return 0;
    }
  }
  out << -1;
  out.close();

  free(numbers);
  free(sum);
  return 0;
}