Cod sursa(job #1067268)

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

using namespace std;

vector<int> numbers;
int n, s, v[10];
int it = 0;
int maxno;
int sofar;
int choice[10];

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

void gen(int current_level) {
  // If you've run out of space, test for solutions.
  if (current_level == 7) {
    if (sofar == s) {
      write_sol_and_quit();
    } else {
      return;
    }
  }

  while (choice[current_level] < numbers.size()) {
    int current_no = numbers[choice[current_level]];

    // Will we underrun with the current choice?
    if (sofar + current_no + (6 - current_level) * maxno < s) {
      choice[current_level]++;
      continue;
    }

    // Will we overrun with the current choice? Stop and backtrack.
    if (sofar + (6 - current_level + 1) * current_no > s) {
      return;
    }

    // Assume the current choice, and then give it up.
    v[current_level] = current_no;
    sofar += current_no;
    choice[current_level + 1] = choice[current_level];
    gen(current_level + 1);
    sofar -= current_no;

    // Advance the choice.
    choice[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());
  maxno = numbers[numbers.size() - 1];

  choice[1] = 0;
  gen(1);

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

  return 0;
}