Cod sursa(job #1067314)

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

using namespace std;

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

  int numbers[200];
  int n, s;
  in >> n >> s;
  for (int i = 0; i < n; ++i) {
    in >> numbers[i];
  }

  std::sort(numbers, numbers + n);

  // Backtrack.
  int choice[10];
  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 < n) {
      // 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;

      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[n - 1] < s) {
        continue;
      }

      // Win or advance the level.
      if (current_level == 6) {
        if (sofar == s) {
          // 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);
        }
      } 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);

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

  return 0;
}