Cod sursa(job #608076)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 14 august 2011 20:48:18
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define infile "loto.in"
#define outfile "loto.out"
#define nMax 131

using namespace std;

vector <int> sums;
vector <int> v;
int n, s, firstGroupSum = -1;

void read() {
  scanf("%d %d\n", &n, &s);
  for(int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    v.push_back(x);
  }
}

int binSearch(vector <int> &v, int x) {
  int le = 0, ri = v.size() - 1, res = 0;
  while(le <= ri) {
    int mi = (le + ri) >> 1;
    if(v[mi] == x) {
      res = mi;
      break;
    } else if(v[mi] < x)
      le = mi + 1;
    else ri = mi - 1;
  }
  return res;
}

void solve() {

  for(unsigned i = 0; i < v.size(); ++i)
    for(unsigned j = 0; j < v.size(); ++j)
      for(unsigned k = 0; k < v.size(); ++k)
        sums.push_back(v[i] + v[j] + v[k]);

  sort(sums.begin(), sums.end());

  for(unsigned i = 0; i < sums.size(); ++i)
    if(sums[binSearch(sums, s - sums[i])] == s - sums[i]) {
      firstGroupSum = sums[i];
      break;
    }
}

void printGroup(int sum) {
  for(unsigned i = 0; i < v.size(); ++i)
    for(unsigned j = i; j < v.size(); ++j)
      if(v[binSearch(v, sum - v[i] - v[j])] == sum - v[i] - v[j]) {
        printf("%d %d %d ", v[i], v[j], sum - v[i] - v[j]);
        break;
      }
}

void write() {
  if(firstGroupSum < 0)
    printf("-1\n");
  else {
    printGroup(firstGroupSum);
    printGroup(s - firstGroupSum);
    printf("\n");
  }
}

int main() {
  freopen(infile, "r", stdin);
  freopen(outfile, "w", stdout);

  read();
  solve();
  write();

  fclose(stdin);
  fclose(stdout);
  return 0;
}