Cod sursa(job #2538897)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 5 februarie 2020 12:22:36
Problema Arbori Scor 0
Compilator cpp-64 Status done
Runda simulare_miri Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

long long dp[95][95][95];

int main() {
  freopen("arbori.in", "r", stdin);
  freopen("arbori.out", "w", stdout);

  int n, m, k;
  scanf("%d%d%dS", &n, &m, &k);
  for (int i = 1; i <= n; ++i)
    dp[i][i - 1][1] = 1;
  for (int i = 2; i <= n; ++i) {
    for (int j = k - 1; j <= i; j += m)
      if (j != -1)
        for (int p = 1; p <= i; ++p)
          dp[i][1][i - 1] += dp[i - 1][j][p];
    for (int j = 2; j <= n; ++j) {
      for (int last = i - 1; last >= 1; --last) {
        bool ok = 0;
        if (dp[i][j][last] == 0)
          dp[i][j][last] = 1;
        for (int p = 1; p <= last; p++)
          if (dp[i - last][j - 1][p])
            dp[i][j][last] *= dp[i - last][j - 1][p], ok = 1;
        dp[i][j][last] *= ok;
      }
    }
  }

  long long ans = 0;
  for (int i = k; i <= n; i += m)
    for (int j = 1; j <= n; j++)
      ans += dp[n][i][j];
  printf("%lld\n", ans);

  return 0;
}