1079 Timus answer/Решение задачи 1079

№1079
http://acm.timus.ru/problem.aspx?space=1&num=1079
ЖМИ ДАЛЕЕ>>>


РЕШЕНИЕ:

PASCAL


Const
ts = 100000;
Var
K,N,I,R: LongInt;
M: Array[1..ts] of LongInt;
Function A(N:LongInt): LongInt;
Var
T: LongInt;
Begin
If M[N]<>0 then begin
A:=M[N];
Exit;
End;
If N=0 then T:=0;
If N=1 then T:=1;
If (N<>1) and (N<>0) then
If Odd(N) then T:=A((N-1) div 2) + A((N-1) div 2+1)
else T:=A(N div 2);
M[N]:=T;
A:=T;
End;
Begin
FillChar(M,SizeOf(M),0);
Readln(N);
For I:=1 to ts do
A(I);
While (N<>0) do begin
R:=0;
For I:=1 to N do
If R<M[I] then R:=M[I];
Writeln(R);
Readln(N);
End;
End.


C++

#include <iostream>
#include <stdlib.h>

using namespace std;

int a[1000000], n, i, _max, x;

int main ()
{
 a[0] = 0;
 a[1] = 1;

 cin >> x;
 while (x != 0)
 {
  for (i = 1; i <= x; i++)
  {
   a[i*2] = a[i];
   a[i*2+1] = a[i]+a[i+1];
   if (a[i] > _max)
    _max = a[i];
  }
  cout << _max << "\n";
  cin >> x;
 }
 return 0;
}


или



#include "iostream"
#include "math.h"
using namespace std;
int main()
{
long a[100001],i;
a[0]=0;
a[1]=1;
for(i=2;i<100001;i++)
{
if(i%2==0)
{
a[i]=a[i/2];
}
else
{
a[i]=a[i/2]+a[i/2+1];
}
}
int t[10];
i=0;
while(true)
{
cin>>t[i];
if(t[i]==0)
break;
i++;
}
i=0;
long max;
while(t[i]!=0)
{
for(int j=0;jmax)
{
max=a[j];
}
}
cout<<max<<"\n";
max=-1;
i++;
}
return 0;
}

1079. Максимум

Ограничение времени: 2.0 секунды
Ограничение памяти: 16 МБ

Рассмотрим последовательность чисел a_i, i = 0, 1, 2, …, удовлетворяющих следующим условиям:

• a₀ = 0
• a₁ = 1
• a_2i = a_i
• a_{2i + 1} = a_i + a_{i + 1}

для каждого i = 1, 2, 3, … .

Напишите программу, которая для заданного значения n находит максимальное среди чисел a₀, a₁, …, a_n.

Исходные данные

Входные данные состоят из нескольких тестов (не более 10). Каждый тест представляет собой строку, в которой записано целое число n (1 ≤ n ≤ 99 999). В последней строке входных данных записано число 0.

Результат

Для каждого n во вводе выведите соответствующее максимальное значение.

Пример

исходные данные	результат
5 10 0	3 4

Автор задачи: Emil Kelevedzhiev
Источник задачи: Winter Mathematical Festival Varna '2001 Informatics Tournament