Обсуждение @ 1013. K-ичные числа. Версия 3 @ Timus Online Judge

Online Judge

Задачи

Авторы

Соревнования

О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки

Архив задач
Отправить на проверку
Состояние проверки
Руководство

Регистрация
Исправить данные
Рейтинг авторов

Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Обсуждение задачи 1013. K-ичные числа. Версия 3

Показать все сообщения Спрятать все сообщения

How can I pass the time limit ? Please help me !!! Nguyen Viet Bang 25 авг 2002 15:26

The algorithms I found requires O(N^2) , which N = 1800 . But we
must calculate the large-number ( I use string) , so it takes about O
(N^3) !!! . Could anyone help me on this Problem ?

Re: How can I pass the time limit ? Please help me !!! Renat Mullakhanov 25 авг 2002 19:38

There is O(N) algorithm based on formula: f(n)=(k-1)*(f(n-2)+f(n-1)).

Some hint Zhou Yiyan@SHU 27 авг 2002 18:03

1 Don't use string, use int array.
2 use larger base to reduce the total operation
3 if C++, don't use STL