ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1079. Maximum

AC with 0.015 sec and 91 kb
Posted by Manastireanu 7 Mar 2005 23:28
find out such x that 2^x < n < 2^(x+1)
2^x means 2*2*...*2 x times

x=log(n)/log(2);//c++


the maximum value of a[i] i=1,2,...,2^x is
max=f(x);
where f(x) is the fibonacci sequence
f(0)=1 f(1)=1 f(n)=f(n-2)+f(n-1)

so i just have to look if there is a larger number from 2^x to n

it is easy to find out the value of a[i] without knowing a[1]...a[i-1]

if l=2*k and r=2*p
m=(l+r)/2
a[m]=a[l]+a[r];

it is rather easy to prove that
a[2^x]=1;
a[2^(x+1)]=1;

so you just have to do a binary search for i from 2^x to 2^(x+1) calculating the values for the left and right border

this is the function that does exactly that //c++
int b(long l,long r,long i,int v1,int v2)
{
long m=(l+r)/2;
if (i==m)    return (v1+v2);
if (i<m)    return j(l,m,i,v1,v1+v2);
        return j(m,r,i,v1+v2,v2);
}


I DON'T UNDERSTAND WHY, BUT WHEN I USE MATH.H I GET COMPILATION ERROR


good luck !!!
Re: AC with 0.015 sec and 91 kb
Posted by Veselin Kolev 24 Apr 2005 23:50
You have to use math instead of math.h ;-)
Read F.A.Q.
Posted by Vladimir Yakovlev (USU) 25 Apr 2005 13:13
Re: AC with 0.015 sec and 91 kb
Posted by Bogatyr 18 Sep 2012 13:28
Manastireanu, thank you for your ideas, they pushed me to more deeply study the sequence.
A few comments:

> if l=2*k and r=2*p, m=(l+r)/2, a[m]=a[l]+a[r];

This is not true for all k and p, e.g., k=4 and p=7.   It is true starting with l=2^x and r = 2^(x+1),  m=(l+r)/2 and then recursing through more (l,r) with (l, m) and (m, r).

There are many interesting properties of this sequence, I encourage everyone to study it and to discover the patterns which will help solve this problem without "brute force", and will help with Maximum2