Discussion @ 1309. Dispute @ Timus Online Judge

No subject

Posted by sloboz 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...

Easier way

Posted by Vlad Veselov 14 Apr 2004 17:59

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

Re: Easier way

Posted by Gheorghe Stefan 15 Apr 2004 05:11

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

No subject

Posted by Vlad Veselov 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.

Re: No subject

Posted by Alex[LSD] 15 Apr 2004 23:26

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

Re: No subject

Posted by A. Mironenko 16 Apr 2004 15:30

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

Re: No subject

Posted by hajime 16 Apr 2004 15:53

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

Re: Easier way

Posted by Vlad Veselov 16 Apr 2004 16:37

I mistaken.

Re: No subject

Posted by A. Mironenko 17 Apr 2004 14:38

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

I've tryed. No way but precalc-fake :( (-)

Posted by Dmitry 'Diman_YES' Kovalioff 17 Apr 2004 16:18

Re: I've tryed. No way but precalc-fake :( (-)

Posted by Denis Koshman 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)

Discussion of Problem 1309. Dispute