Cod sursa(job #1447587)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 4 iunie 2015 19:46:09
Problema Combinari Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>

using namespace std;

int n, k, a[20];
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;
}

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;
}

/*

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
2 3 4
2 3 5
...
3 4 5

   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

*/