Rabbit problem

problem11_rabbit.cpp

/*
 В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, 
 директор зоопарка распорядился поставить в его клетке лесенку. 
 Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. 
 Лестница имеет определенное количество ступенек 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 различных маршрутов добраться до вершины лестницы.
	
Входные данные

В единственной строке входного файла INPUT.TXT записаны два натуральных
числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое 
может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.
Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных
вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей. 
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>

using namespace std;

struct longnum {
	string num;

	void add(longnum n) {
		string res = "";
		int r = 0;
		for (int i = 0; i < min(num.length(), n.num.length()); i++) {
			r += (num[i]-'0') + (n.num[i] - '0');
			if (r > 9) {
				res.push_back((r % 10) + '0');
				r /= 10;
			}
			else {
				res.push_back(r + '0');
				r = 0;
			}
		}
		if (num.length() != n.num.length()) {
			string s = num.length() > n.num.length() ? num : n.num;
			for (int i = min(num.length(), n.num.length()); i < s.length(); i++) {
				r += (s[i]-'0');
				if (r > 9) {
					res.push_back((r % 10) + '0');
					r /= 10;
				}
				else {
					res.push_back(r + '0');
					r = 0;
				}
			}
		}
		while (r != 0) {
			res.push_back((r % 10) + '0');
			r /= 10;
		}
		num = res;
	}
	void set(string n) {
		num = n;
	}

	longnum(string n) {
		set(n);
	}

	longnum() {
		num = "0";
	}
};

int main(int argc, char ** argv) {   
	ifstream in("INPUT.TXT");
	ofstream out("OUTPUT.TXT");

	int n = 0, k = 0;
	in >> k >> n;
	vector<longnum> jmp(n);

	for (int i = 0; i < k; i++) {
		jmp[i].set("1");
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < min(n, i + k + 1); j++) {
			jmp[j].add(jmp[i]);
		}
	}

	string res = jmp[jmp.size()-1].num;
	reverse(res.begin(), res.end());
	out << res << endl;

	in.close();
	out.close();
}