Идея у меня такая: поднимаясь на следующую ступеньку, ставим n-2 кубиков (это становится новое основание), дальше пытаемся сдвинуть эту группу кубиков вправо, попутно проверяя возможность подняться наверх. Уменьшаем эту группу на 1, повторяем. Если какой-то из функций достигается нужный уровень, т.е. k, то кол-во вариантов увеличиваем.
Рекурсию никогда раньше не использовал, попробова, вот, что получилось:
#include <iostream>
using namespace std;
int step(int, int, int);
int main ()
{
int n,k,otv=0;
cin>>n>>k;
otv+=step(n,k,1);
cout<<otv;
return 0;
}
int step(int x, int y, int z)
{
int l,r,size,st,l2,r2,sum=0;
st=z;
size=x;
if (size-2>=1) //возможна ли следующая ступенька
{
r=size-1;
l=size-r;
size=size-2;
st++;
while (l!=r) //уменьшение кубиков на ступеньке
{
l2=l;
r2=r;
while (r2<size) //сдвиг кубиков на ступеньке
{
if ((r-l>2) && (st<=y)) step(size,y,st); //подъем наверх
l2++;
r2++;
}
r--;
}
if (st==y) sum++;
}
return sum;
}
Выдает либо 0, либо 1...