Олимпиадная задача про зайца

#алгоритм

Один мой знакомый занимается составлением олимпиадных задач, которые впоследствии
иногда дают на собеседованиях. Возникли затруднения с решением данной задачи:


  В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно,
директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может
прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное
количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для
разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору
любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при
заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить
это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1,
1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных
маршрутов добраться до вершины лестницы.  


Хотелось бы узнать, что предложите вы. Мне интересен сам алгоритм, код далеко не
так важен, но в любом случае это будет только плюсом =)
    

Ответы

Ответ 1

Простейшая динамика (в которой я очень слаб, к сожалению)
Заведем массив dp размерностью n+1 (каждый i-й элемент будет хранить количество если
бы было i ступенек)
dp[0]=1 //ступенек нет

Остальные рассчитываются как сумма всех предыдущих на расстоянии не больших k
Ответ в dp[n]. 
upd тоже код с acmp.ru
a[0] = BigInteger.ONE;
        int start;
        for (int i=1; i<=n; i++)
        {
            start = Math.max(0, i-k);
            a[i] = BigInteger.ZERO;
            for (int j=start; j
Ответ 2

Вот эта задача на сервере acmp.ru. Решал её несколько лет назад. Там динамика действительно
очень простая, но дополнительная сложность была в ограничениях на K и N (1 ≤ K ≤ N
≤ 300). Для граничных значений K и N результат не помещался даже в 64-битной переменной,
поэтому приходилось привлекать длинную арифметику.
К сожалению, нет сейчас времени думать над педагогическими аспектами вопроса - как
бы так намекнуть, но не раскрыть решение. Поэтому, надеясь на честность автора, приведу
свой зачтенный код. Автору вопроса предлагаю подумать, как его улучшить (улучшать есть
куда - писал на скорость, олимпиадная задача все-таки).
#include

#define INFILE "INPUT.TXT"
#define OUTFILE "OUTPUT.TXT"

int m[400][100];

int main()
{
    FILE *fin, *fout;
    long k, n, i, j, t, z, w;

    fin = fopen(INFILE, "r");
    fscanf(fin, "%d%d", &k, &n);
    fclose(fin);

    fout = fopen(OUTFILE, "w");
    for (i = 0; i < n; i++)
    {
        if (i < k) m[i][0] = 1; else m[i][0] = 0;
        for (j = (0 > i - k ? 0 : i - k) ; j <= i - 1 ; j++)
        {
            z = 0;
            for(t = 0 ; t < 100; t++)
            {
                w = m[i][t] = m[i][t] + m[j][t] + z;
                m[i][t] = w % 10;
                z = w / 10;
            }
        }

    }
    t = 99;
    while (m[n - 1][t] == 0) t--;
    for(;t >= 0; t--) fprintf(fout, "%d", m[n - 1][t]);
    fclose(fout);
}


Ответ 3

Мой порядок рассуждений...

случай 1, считаем минимальное кол-во прыжков, вводим н и к
н делим на к - получаем минимальное кол-во прижков + остаток

остаток можно разбить или на единици или на 1 + часть < k, а они точно меньше будет,
тут надо еще додумать... 


случай 2, когда заяц всю н проскачет по 1


случай 3, когда заяц не будет прыгать свое к


помогайте дальше... =)


Ответ 4

#include 
#include 

static int result = 0;
static int k;
static int n;

void tryCount(int a)
{
    if (a == n)
    {
        ++result;
        return;
    }

    for (int i = 1; i <= k; ++i)
    {
        if (a < n)
        {
            a += i;
            tryCount(a);
            a -= i;
        }
    }
}

int main()
{
    std::ifstream in("INPUT.TXT", std::ios::in);
    std::ofstream out("OUTPUT.TXT", std::ios::out);

    in >> k;
    in >> n;
    in.close();

    tryCount(0);

    out << result;
    out.close();
}

Своего рода бектрекинг. Вот только сдать этот ответ на сайте с заданием не получиться.
Время на затрат рекурсии ~ 1,350 sec c данными сайта. На моей машине это время приблизительно
соответствует значению k = 5, n = 20. Пробовал занести в регистр процессора int a,
int i - время сократилось чуть больше чем на 30% (~ 0,95 sec), вот только эта функция
отлючена в компиляторе на сервере(