#include <iostream>
#include <cmath>
#include <cstdlib>

int getWrongMoves(int n, int k)
{
    int result = 1;
    for (int i = 1; i < n - k; ++i)
    {
        result = 2 * result + i;
    }
    return  result;
}

int main(int argc, char *argv[])
{
    int n = 0;
    int k = 0;

    if (argc > 2)
    {
        n = atoi(argv[1]);
        k = atoi(argv[2])+1;
    }
    if (n < 1 || n > 100)
    {
        std::cout << "Usage: zenik <N>, <K>\n"
                  " where 1 <= N, K <= 100" << std::endl;
        return 0;
    }

    double allMoves = std::pow(2, n-1);
    double wrongMoves = 0;

    if (k == 1)
    {
        wrongMoves = allMoves - 1;
    }
    else if (k >= n)
    {
        wrongMoves = 0;
    }
    else
    {
        wrongMoves = getWrongMoves(n, k);
    }

    std::cout << "all moves: " << allMoves <<  std::endl;
    std::cout << "wrong moves: " << wrongMoves <<  std::endl;
    std::cout << "corect moves: " << allMoves - wrongMoves <<  std::endl;

    return 0;
}

all moves: 16
wrong moves: 3
corect moves: 13

10000 - зразу на останню сходинку, пропустили 4 сходинки
10001 - з першої на останню сходинку, пропустили 3 сходинки
11000 - зразу на передостанню, пропустили 3 сходинки

long long go(int size, long long min, long long max)//min, max можуть бути int-ами
{
 if (max - min > k)
  return 0;
 long long x = 0;
 if (size != n)
  if (memo[size][min][max] != -1)
   return memo[size][min][max];
 for (int i = 1; i <= n; i++)
 {
  if (size - i >= 0 && max - min <= k)//ми вже перевіряли max-min, а size-i>=0 можна внести в умову циклу
   x += go(size - i, Min(min, i), Max(max, i)) % ost;
  if (max - min > k)//це ніколи не виконається
   return 0;
  if (size == 0 && max - min <= k)//це можна винести на початок
   return 1;
 }
 if (size != n)
  memo[size][min][max] = x;
 return x;
}

long long go(const int size, const int min, const int max)
{
 if (max - min > k)
  return 0;
 if (size != n && memo[size][min][max] != -1)
   return memo[size][min][max];
 if (size == 0)
  return 1;
 long long x = 0;
 for (int i = 1; i <= size; i++)
 {
   x += go(size - i, Min(min, i), Max(max, i)) % ost;
 }
 if (size != n)
  memo[size][min][max] = x;
 return x;
}