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

I can't work it out.
Posted by hydra 12 Oct 2001 09:42
I want to know if we can use a mathematical way to solve
problem 1079.Now I only can do it use dynamic
programming,which costs too much memory about 1M.I't would
get memory exceeded error.But if not so,My program has to
spend too much time to do a lot of redundant calculation.
Here is the recursion program:

var i,n,s:longint;
    max:word;
    bf:word;
function f(n:longint):word;
begin
 while n and 1=0 do n:=n shr 1;
 if n=1 then f:=1
  else
  begin
   n:=n shr 1;
   f:=f(n+1)+f(n);
  end;
end;
begin
 readln(n);
 while n<>0 do
  begin
   max:=0;
   i:=1;
   while i<=n do
    begin
     bf:=f(i);
     if bf>max then begin max:=bf;s:=i;end;
     inc(i,2);
     write(i,':',bf,' ');
    end;
   writeln;
   writeln(max,' ',s);
   readln(n);
  end;
end.

It would get time exceeded error!?!
Re: I can't work it out.
Posted by zyzyis 27 Mar 2002 08:45
I agreed with you ,but i can't find the mathematical way
by far



> I want to know if we can use a mathematical way to solve
> problem 1079.Now I only can do it use dynamic
> programming,which costs too much memory about 1M.I't would
> get memory exceeded error.But if not so,My program has to
> spend too much time to do a lot of redundant calculation.
> Here is the recursion program:
>
> var i,n,s:longint;
>     max:word;
>     bf:word;
> function f(n:longint):word;
> begin
>  while n and 1=0 do n:=n shr 1;
>  if n=1 then f:=1
>   else
>   begin
>    n:=n shr 1;
>    f:=f(n+1)+f(n);
>   end;
> end;
> begin
>  readln(n);
>  while n<>0 do
>   begin
>    max:=0;
>    i:=1;
>    while i<=n do
>     begin
>      bf:=f(i);
>      if bf>max then begin max:=bf;s:=i;end;
>      inc(i,2);
>      write(i,':',bf,' ');
>     end;
>    writeln;
>    writeln(max,' ',s);
>    readln(n);
>   end;
> end.
>
> It would get time exceeded error!?!
>