Обсуждение @ 1309. Искусство спора @ Timus Online Judge

No subject

Послано sloboz 14 апр 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

Послано Vlad Veselov 14 апр 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

Послано Gheorghe Stefan 15 апр 2004 05:11

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

No subject

Послано Vlad Veselov 15 апр 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

Послано Alex[LSD] 15 апр 2004 23:26

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

Re: No subject

Послано A. Mironenko 16 апр 2004 15:30

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

Re: No subject

Послано hajime 16 апр 2004 15:53

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

Re: Easier way

Послано Vlad Veselov 16 апр 2004 16:37

I mistaken.

Re: No subject

Послано A. Mironenko 17 апр 2004 14:38

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

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

Послано Dmitry 'Diman_YES' Kovalioff 17 апр 2004 16:18

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

Послано Denis Koshman 2 авг 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)

Обсуждение задачи 1309. Искусство спора