Обсуждение @ 1098. Questions @ Timus Online Judge

Timus Online Judge

Online Judge	Задачи	Авторы	Соревнования
О системе Часто задаваемые вопросы Новости сайта Форум Ссылки	Архив задач Отправить на проверку Состояние проверки Руководство	Регистрация Исправить данные Рейтинг авторов	Текущее соревнование Расписание Прошедшие соревнования Правила

вернуться в форум

Обсуждение задачи 1098. Questions

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

It is a Joseph problem.If you have read Concrete Mathematics,you can solve it easily in O(N), Andrew 14 июл 2004 19:28

Re: It is a Joseph problem.If you have read Concrete Mathematics,you can solve it easily in O(N), Igor E. Tuphanov 10 июл 2006 14:18

How's that? FE, it seems to me, my solution works for O(logn), where n is the length of text and the base of logarithm is 1999/1998.

Re: It is a Joseph problem.If you have read Concrete Mathematics,you can solve it easily in O(N), Anisimov Dmitry 6 окт 2008 21:12

Igor, it seems wrong because your solution has exactly same asymptotical order.
O(ln X/ln(N/(N-1)) = O(ln X/(ln(1+1/N))= O(N*ln X)