Cod sursa(job #1022847)

Utilizator NCodeMihai X NCode Data 6 noiembrie 2013 00:07:10
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct sum3 {
  int a, b, c;
  int sum;
  sum3() {
  }
  sum3(int t1, int t2, int t3) : a(t1), b(t2), c(t3), sum(t1 + t2 + t3) {
  }
};

bool CompSum3(const sum3 &s1, const sum3 &s2) {
  return s1.sum < s2.sum;
}

int Search(const vector<sum3> &sum, int st, int dr, int val) {
  if (st > dr) {
    return -1;
  }

  int mid = (st + dr) / 2;

  if (sum[mid].sum == val) {
    return mid;
  }
  if (val < sum[mid].sum) {
    return Search(sum, st, mid - 1, val);
  }
  return Search(sum, mid + 1, dr, val);
}

int Search(const vector<sum3> &sum, int val) {
  return Search(sum, 0, sum.size() - 1, val);
}

int main() {
  int s;
  unsigned i, j, k, n;

  ifstream in("loto.in");
  in >> n >> s;
  vector<int> numbers(n);
  for (i = 0; i < n; ++i) {
    in >> numbers[i];
  }
  in.close();

  vector<sum3> sum;
  for (i = 0; i < n; ++i) {
    for (j = 0; j < n; j++) {
      for (k = 0; k < n; k++) {
        sum.push_back(sum3(numbers[i], numbers[j], numbers[k]));
      }
    }
  }

  std::sort(sum.begin(), sum.end(), CompSum3);
  
  int r;
  ofstream out("loto.out");
  for (i = 0; i < sum.size(); ++i) {
    r = Search(sum, i + 1, sum.size() - 1, s - sum[i].sum);
    if (r != -1) {
      out << sum[i].a << " " << sum[i].b << " " << sum[i].c << " " <<
        sum[r].a << " " << sum[r].b << " " << sum[r].c;
      out.close();
      return 0;
    }
  }
  out << -1;
  out.close();
  return 0;
}