Cod sursa(job #1067310)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 26 decembrie 2013 17:53:40
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;

vector<int> numbers;
int n, s;
int choice[10];

void write_sol_and_quit() {
  ofstream out("loto.out");
  for (int i = 1; i <= 6; ++i) {
    out << (i == 1 ? "" : " ") << numbers[choice[i]];
  }
  out << std::endl;
  out.close();
  exit(0);
}

void gen() {
  int sofar = 0;
  int current_level = 1;
  bool just_strepped[10] = { false };
  choice[1] = -1;
  just_strepped[1] = true;
  do {
    while (choice[current_level] + 1 < numbers.size()) {
      // Make a new choice for the current level, and assume it.
      if (!just_strepped[current_level]) {
        sofar -= numbers[choice[current_level]];
      }
      choice[current_level]++;
      sofar += numbers[choice[current_level]];
      just_strepped[current_level] = false;

      // Print state:
      //for (int i = 1; i <= current_level; ++i) {
      //  std::cerr << (i == 1 ? "" : " ") << numbers[choice[i]];
      //}
      //std::cerr << std::endl << sofar << std::endl << std::endl;

      // If this choice is going to overrun, give it up and backtrack.
      if (sofar + (6 - current_level) * numbers[choice[current_level]] > s) {
        sofar -= numbers[choice[current_level]];
        break;
      }

      // If we're underruning, give up the choice and continue.
      if (sofar + (6 - current_level) * numbers[numbers.size() - 1] < s) {
        continue;
      }

      // Win or advance the level.
      if (current_level == 6) {
        if (sofar == s) {
          write_sol_and_quit();
        }
      } else {
        current_level++;
        choice[current_level] = choice[current_level - 1] - 1;
        just_strepped[current_level] = true;
      }
    }

    // Ran out of choices, decrease the level anyway.
    current_level--;

  } while (current_level);
}

int main()
{
  ifstream in("loto.in");

  in >> n >> s;
  for (int i = 0; i < n; ++i) {
    int x;
    in >> x;
    numbers.push_back(x);
  }

  std::sort(numbers.begin(), numbers.end());

  gen();

  // If it returned, that's bad news.
  ofstream out("loto.out");
  out << "-1\n";
  out.close();

  return 0;
}