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

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)

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