Cod sursa(job #1022855)

Utilizator NCodeMihai X NCode Data 6 noiembrie 2013 00:20:12
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 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) {
  }
  inline int Sum() const{
    return a + b + c;
  }
};

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) {
  int x;
  while (st <= dr) {
    int mid = (st + dr) / 2;
    
    x = sum[mid].Sum();
    if (x == val) {
      return mid;
    }
    if (val < x) {
      dr = mid - 1;
    } else {
      st = mid + 1;
    }
  }
  return -1;
}

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;
  int sum_i;
  ofstream out("loto.out");
  for (i = 0; i < sum.size(); ++i) {
    sum_i = sum[i].Sum();
    if (sum_i + sum_i == s) {
      out << sum[i].a << " " << sum[i].b << " " << sum[i].c << " " <<
        sum[i].a << " " << sum[i].b << " " << sum[i].c;
      out.close();
      return 0;
    }

    r = Search(sum, i + 1, sum.size() - 1, s - sum_i);
    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;
}