ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1079. Максимум

I can't work it out.
Послано hydra 12 окт 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.
Послано zyzyis 27 мар 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!?!
>