Cod sursa(job #811444)

Utilizator juniorOvidiu Rosca junior Data 12 noiembrie 2012 12:51:22
Problema Combinari Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>

using namespace std;

int n, k, a[10];
ifstream fi("combinari.in");
ofstream fo("combinari.out");

void init (int i) {
    a[i] = a[i-1];
}

bool succesor (int i) {
  a[i]++;
  return a[i] <= n - k + i;
}

bool valid (int i) {
  return true; // Orice valoare aleasa in succesor este corecta.
}

int sol (int i) {
   return i == k; // Am completat toate cele k locuri?
}

void tip () {
  int j;

  for (j = 1; j <= k; j++)
    fo << a[j] << ' ';
  fo << '\n';
}

void bt (int i) {     // Exact dupa forma generala.
  init (i);           // initializare
  while (succesor(i)) // cat timp avem un succesor
    if (valid(i))     // sunt indeplinite conditiile?
      if (sol(i))     // avem o solutie completa
        tip();        // prezentam solutia
      else            // nu?
        bt(i + 1);    // trecem la nivelul urmator
}

int main () {
  fi >> n >> k;
  bt(1);
  return 0;
}

/*
Deducerea formulei din linia 13 ("a printesei"):

   i      max
----------------
   n       k
  n-1     k-1      Diferenta i-max este constanta: i-max = n-k => max = n-k+i
  n-2     k-2
*/