@PRIYD

Что не так в использовании длинной арифметики?

Здравствуйте, решал задачу(условие под спойлером) и, кажется, решил правильно, но падает на 10 тесте. Насколько я понимаю, проблема в моей неправильной реализации длинной арифметики. Буду признателен за помощь.
Условие
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек 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 <vector>
#include <algorithm>

using namespace std;
typedef unsigned long long ull;

const ull BASE = 1e9;
const ull SIZE = 15;

vector<ull> formBI(ull num) {
	vector<ull> res(SIZE, 0);

	short i = 0;
	while (num) {
		res[i++] = num % BASE;
		num /= BASE;
	} 

	return res;
} 

vector<ull> sum(vector<ull> n1, vector<ull> n2) {
	for (size_t i=0; i<SIZE; i++) {
		n1[i] += n2[i];
	}	

	for (size_t i=0; i<SIZE-1; i++) {
		if (n1[i]>=BASE) {
			n1[i] -= BASE;
			n1[i+1]++;
		}
	}
	
	return n1;
}

void print(vector<ull> n) {
	reverse(n.begin(), n.end());

	for(size_t i=0; i<SIZE; i++) {
		if (n[i]!=0) {
			cout << n[i];
		}
	}	

	cout << endl;
}

int main() {
	short k, n;
	cin >> k >> n;
	
	vector<ull> emp(SIZE, 0);
	vector<vector<ull>> b(n+1, emp); 
	b[0] = formBI(1);
	
	for (size_t i=1; i<n+1; i++) {
		short r = (i<k) ? i : k;
		
		for (size_t j=1; j<=r; j++) {
			b[i] = sum(b[i], b[i-j]);
		}
	}

	print(b[n]);
	return 0;
}

  • Вопрос задан
  • 75 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Проблема в выводе. Вы нулевые цифры вообще не выводите:
for(size_t i=0; i<SIZE; i++) {
  if (n[i]!=0) {
    cout << n[i];
  }
}


А нужно пропускать только ведущие нули. Самый простой способ исправить - завести bool printed:
bool printed = false;
for(size_t i=0; i<SIZE; i++) {
  if (printed || n[i]!=0) {
    cout << n[i];
    printed = true;
  }
}


Ну, еще может быть стоит увеличить размер длинных чисел. Не факт, что 135 цифр хватит. Введите тест n=300, k=300, и проверьте что выводится один и тот же ответ при текущем и увеличенном SIZE.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
17 янв. 2021, в 08:35
50000 руб./за проект
17 янв. 2021, в 01:26
100000 руб./за проект
16 янв. 2021, в 22:34
10000 руб./за проект