Cod sursa(job #2255223)

Utilizator gabrielmGabriel Majeri gabrielm Data 6 octombrie 2018 16:48:54
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int v[100];
int n, s;

int solutie[6];

bool bt(int k, int suma, int* dr) {
  if (k == 6) {
    // bingo
    if (suma == s) {
      return true;
    } else {
      return false;
    }
  }

  // Daca adaugam un element mai mare decat `max`,
  // depasim suma tinta
  int max = s - suma;

  int* it = upper_bound(v, v + n, max) - 1;

  while (it >= v) {
    int val = *it--;

    solutie[k] = val;

    if (bt(k + 1, suma + val, it)) {
      return true;
    }
  }

  return false;
}

int main() {
  ifstream in("loto.in");
  in >> n >> s;

  for (int i = 0; i < n; ++i) {
    in >> v[i];
  }

  ofstream out("loto.out");

  if (bt(0, 0, v + n)) {
    for (int i = 0; i < 6; ++i) {
      cout << solutie[i] << ' ';
    }
    cout << '\n';
  } else {
    cout << "-1\n";
  }
}