With help of my friend that was just looking at maximums index sequense and found an idea, finally, I got AC.
Some hints:
1) Find an idea to calculate next maximum indices from previous ones: all the maximum's indices can be obtained from previous ones in such ways:
i = s*2 + 1; or
i = s*2 - 1; or
i = s*4 + 1; or
i = s*4 - 1;

for example f(21)=8 is maximum for 21<=n<=34
so 21 = 2*11-1, where 11 is one of previous maximums indices. And so on using all the formulas above.
but 2*11+1 = 23 is not a maximum index. so we have to cancel  this number (23).
2) Learn to calculate f(n) in O(logn)
3) Generate all maximums indices (about 1500). You can store them in heap to get an access to the smallest maximum index.
4) than read n and just search for it in maximums index array.
P.S. who can prove the first and the main idea? If you can, please post here you proof.

Suppose we want to calculate max({A * a[i] + B * a[i + 1], A * a[i + 1] + B * a[i]}) for i = 0..n-1 (in this problem A = 0, B = 1). Then answer(A, B, n) = max(answer(max(A, B), A + B, n/2), A * a[n - 1] + B * a[n], B * a[n - 1] + A * a[n]), so it can be solved recursively.

I think that most people trying to solve this problem will try to deal with two problems, they are:
1. How to calculate a[n] fast?
2. How to find those n that a[n] is the maximum in [1...n]?
Here is my method.

1. Calculating a[n] (without calculating a[1...n-1]).
Directly calculation will lead to a long time.
But, after some observation, I found that:
a[4n] = a[n]
a[4n + 1] = a[2n] + a[2n + 1] = 2a[n] + a[n + 1]
a[4n + 2] = a[n] + a[n + 1]
a[4n + 3] = a[n] + 2a[n + 1]
So, a[4n] to a[4n + 3] could be presented as the linear form of a[n] and a[n + 1].
We will soon realise that, a[2^k n] to a[2^k n + (2^k - 1)]  could also be presented as linear form of a[n] and a[n + 1].
So, pre-calculation is done to calculate all the linear forms of a[65536n] to a[65536n + 65535]. This will take about O(65536 * 2) time.
After this pre-calc, calculation for any number K will go very fast.

2. Finding the maximum.
After listing some of the 'maximum index', we found that:
1
3
5
9
11
19
21
35
37
43
......
Maybe my math is not so good, so I could not find so useful properties in the array, but I noticed one thing:
------------------------------------------------------------------------------------------
Every 'maximunm index' could be presented as its max 2-power and some former 'maximum index'.
------------------------------------------------------------------------------------------
Sorry for my poor English, let's take a look at the examples:
1
3 = 2 + 1
5 = 4 + 1
9 = 8 + 1
11 = 8 + 3
19 = 16 + 3
21 = 16 + 5
35 = 32 + 3
37 = 32 + 5
43 = 32 + 11
......
So, we just need to use every 2^k number to ITERATE the list of 'maximum index'. As the list is of size O(Log N), the algo runs quite fast.

With above methods, I got AC in 0.046 sec.

Well, if my algo is too stupid for you, don't hesitate to post your algo here.

Have fun and good luck.

I've solved 1079,but this problem...Is any trick there?

Edited by author 01.09.2007 22:19

One way to solve this problem has something to do with binary representation and fibonacci sequence.. or tree traversal on odd numbers.

I received incomparable pleasure of solving this problem. Vladimir, Thanx. :)

I submitted my program to 1079 and get AC.
It at least shows that my ALGO work for small data.

By the way, my answer for 10^18 is
2504730781961
Is it right?

Maybe the 'int64' or some problems like this make me WA.
Could you please tell me why? I am confused.

Thanks in advance.

http://www.research.att.com/~njas/sequences/A002487
http://www.research.att.com/~njas/sequences/A091945

Edited by author 05.07.2009 21:08

I HAVE ACCEPTED WITHOUT PRECALCULATE!!!!!!!!!! MY PROG SOLVE THIS PROBLEM FOR 0.046 ms AND USE 650 kb. I think, that limitation must be bigest: For Example 10^180.

Last line before Sample:
corResponding

I've passed with O(TLogN) but I can't solve with O(T). Please help me with the algorithm O(T). My email is : phongpdnkptnk_4ever@yahoo.com

I've solved this problem, but in quite a sophisticated way. How did you solve it? May write here or at nick@inbox.ru, using goryinyich as the nick.

What is test#1 or test #2?I've solved 1079,but my program gives Crash on #1 test in 1396. Please answer/Thank!!!

Edited by author 28.07.2007 22:21

Please I need any tips why I am having WA#1. My solution was accepted at 1079 and it is O(logN) solution. May be some subtle issues with the compiler and __int64 stuff? I cannot debug on my computer because it does not have __int64.

Nice task... I really like it...
Not very difficult, but not simple too

<Editted>

Edited by author 21.03.2007 15:34

I have AC

Edited by author 01.10.2006 05:51

This problem is the same as 1079 “Maximum” but with bigger limitations.

Edited by author 10.05.2006 19:37