Discussion @ 1309. Dispute @ Timus Online Judge

sloboz No subject [10] // Problem 1309. Dispute 14 Apr 2004 08:13

easy, you just generate the solutions for 0..100 millions and then you just calculate 1 million values with that algorithme...

Vlad Veselov Easier way [9] // Problem 1309. Dispute 14 Apr 2004 17:59

f(n) depends only from f(n-1), there are 9973 different values, so you can find the period.

Gheorghe Stefan Re: Easier way [7] // Problem 1309. Dispute 15 Apr 2004 05:11

i don't understand. there may be no period
you got AC like this?

Vlad Veselov No subject [6] // Problem 1309. Dispute 15 Apr 2004 18:14

Can be only 9973 different values of f(n) (0 .. 9972). For each of them we will remember, have we already get it or not. Not more than after 9973 steps we will see repeat. Sequence look like this:
a b c ... d (e f g ... h) e ... . Part in brackets is the period.
I haven't tried to solve it yet.

Alex[LSD] Re: No subject [5] // Problem 1309. Dispute 15 Apr 2004 23:26

Well Vlad. It also depends on N as far as I see...

A. Mironenko Re: No subject [4] // Problem 1309. Dispute 16 Apr 2004 15:30

Right you are.
This function doesn't have period shorter then 3000000 :^)

hajime Re: No subject [3] // Problem 1309. Dispute 16 Apr 2004 15:53

hi, is there any way to solve it without precalculation ??

A. Mironenko Re: No subject [2] // Problem 1309. Dispute 17 Apr 2004 14:38

At least it is uknown to authors of this problem :)

Dmitry 'Diman_YES' Kovalioff I've tryed. No way but precalc-fake :( (-) [1] // Problem 1309. Dispute 17 Apr 2004 16:18

Denis Koshman Re: I've tryed. No way but precalc-fake :( (-) // Problem 1309. Dispute 2 Aug 2008 14:18

f(n+MOD*k) = A*f(n) + B for any 'n'. Just find A and B in O(MOD) and get the result in O(N/MOD + N%MOD)

Vlad Veselov Re: Easier way // Problem 1309. Dispute 16 Apr 2004 16:37

I mistaken.

Discussion of Problem 1309. Dispute