#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    int a[100000];
    a[0] = 0;
    a[1] = 1;
    int max = 1;
    while(cin >> n, n != 0){
        if(n > max){
            for(int i = max + 1; i <= n; ++i){
                if(i % 2 == 0){
                    a[i] = a[i / 2];
                }
                else{
                    a[i] = a[(i - 1) / 2] + a[(i - 1) / 2 + 1];
                }
                max = n;
            }
        }
        cout << a[n - (n % 2 == 0)] << "\n";
    }
}

Edited by author 10.01.2021 03:55

1.declare an array.size 1000000
2.genarate all number according the problem description.
3.input the value n.
4.declare a container and take the value of the array .vector<int>v(a,a+n);
5.sort the container.
5.at last print v[n];

Edited by author 26.07.2020 04:57

Edited by author 26.07.2020 04:58

import java.util.*;
public class Maximums {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int N = -564646878;   // random value hehehehe
        while (N != 0) {
            N = scn.nextInt();
            if (N == 0) {
                break;     // As per the problems requirement it should terminate at 0
            } else if (N == 1) {
                System.out.println(1);
            } else {
                N = N + 1;    // problems indexing are upto N
                int[] arr = new int[N];    // creating an array to create desired sequence
                arr[0] = 0; arr[1] = 1;   // initialising the array with the given values in question
                int max = Integer.MIN_VALUE;  // to start with
                for (int i = 2; i < N; i++) {
                    if (i % 2 == 0) {
                        arr[i] = arr[i / 2];     // for even indexes
                        if (arr[i] > max) {
                            max = arr[i]; // comparing
                        }} else {
                        arr[i] = arr[(i - 1) / 2] + arr[((i - 1) / 2) + 1];  // for odd indexes
                        if (arr[i] > max) {
                            max = arr[i];// comparing
                        }}}
                System.out.print(max);   // finally printing the max value upto the given index 'N'.
                System.out.println();   // for new line ( P.S. I know i could have made the upper line to println but that's boring
                }}}} /// Happy Coding Dudes n Dudettes

why is the 10th element 4? isn't it 3?

You can solve the question very fast with appropriate precomputed values.
The sequence is known as the Stern-Brocot sequence, I was not aware of it before!

what is test 4. plz help me.
my code is below
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long n=1000,i,k;
    long long a[100000];
    a[0]=0,a[1]=1;
    for(i=2;i<n;i=i+2){
            k=i/2;
        a[i]=a[k],a[i+1]=a[k]+a[k+1];
    }
    cin>>n;
    while(n){
            cout<<*max_element(a,a+n+1)<<endl;
        cin>>n;
    }
}

Edited by author 22.06.2019 13:46

#include <iostream>
int n,x;
int a[10];
int i,t;

int _max(int s1,int s2,int x)
{
    if (x==n)
        return s1+s2;
    else {
        int t1,t2;
        if (x*2-1<=n)
            t1 = _max(s1,s2+s1,x*2-1);
        else
            t1 = 0;
        if (x*2+1<=n)
            t2 = _max(s1+s2,s2,x*2+1);
        else
            t2 = 0;
        if ((t1==t2)&&(t2==0))
            return s1+s2;
        else
            return t1>t2?t1:t2;
    }
}

int main()
{
    std::cin >> n;
    i = 0;
    while (n){
        if (n==2)
            a[i] = 1;
        else
        if (n==1)
            a[i] = 1;
        else
        if (n==0)
            a[i] = 0;
        else
            a[i] = _max(1,1,3);
        std::cin >> n;
        i++;
    }
    for (n = 0;n<i;n++)
        std::cout << a[n] << "\n";

    return 0;
}

int main()
{
    long int n,res;

    while(1){
        scanf("%ld",&n);
        if(n!=0){
    if(n%2==0){
         res=function(n-1);
         printf("%ld\n",res);
    }
    else{
         res=function(n);
            printf("%ld\n",res);
    }

        }
    else{
        return 0;
    }

    }
//gives right ans in codeblocks but here gives WA....Why??
    return 0;

    }


long int function(long int n){
    if(n==1){
        return 1;
    }
    if(n%2==0){
        return 1;
           }
    else if(n%2==1){
        return function(n/2)+function(n/2+1);
            }

                }

a

PS. У меня тесты проходит
PSS. базовые)

#include<iostream>
#include<vector>
using namespace std;

int test(int a);
vector<int> list;
//vector<int> answers;

int main()
{
    list.push_back(0);
    list.push_back(1);
    int N;
    cin >> N;
    while (N != 0)
    {
        cout << test(N);
    //    answers.push_back(test(N));
        cin >> N;
    }
    //for (int i = 0; i < answers.size(); i++)
    //    cout << answers[i] << endl;
    return 0;
}

int test(int a)
{
    int i = 2;
    if (a < list.size() && a % 2 == 0)
        return list[a - 1];
    else if (a < list.size() && a % 2 != 0)
        return list[a];
    else if (a >= list.size())
        i = list.size();
    for (i; i <= a; i++)
    {
        if (i % 2 == 0)
            list.push_back(list[i / 2]);
        else
            list.push_back(list[i / 2] + list[i / 2 + 1]);
    }
    if (a % 2 == 0)
        return list[a - 1];
    else
        return list[a];
}

#include<stdio.h>
#include<string.h>
int main()
{
    int n,i=0,j,temp=0;
    int a[99999];
    int b[20];
    scanf("%d",&b[0]);
    while(b[i]!=0)
    {
        i++;
        scanf("%d",&b[i]);
    }
    n=i;
    a[0]=0;
    a[1]=1;
    for(i=2;i<99999;i++)
    {
        if(i%2==0)
            a[i]=a[i/2];
        else
            a[i]=a[i/2]+a[i/2+1];
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<=b[i];j++)
        {
            if(a[j]>temp)
            {
                temp=a[j];
            }
        }
        printf("%d\n",temp);
    }
    fflush(stdin);
    getchar();
    return 0;
}

I know that my algorithm exactly correct but only mathematically but not in program

var n1:longword;
function max(n:longword):word;
begin
  max:=max+(n mod 2);
  if (n<>1) then
  if n mod 2=0 then
    max(n div 2)
  else
  begin
    max(n div 2);
    max((n div 2)+1);
  end;
end;

begin
  readln(n1);
  writeln(max(n1));
  readln;
end.

Maybe I do not fully understand how do recursive functions operate.

Edited by author 02.04.2016 15:07

n=1
x=[]
while(n<=10):
    j=int(input())
    if j==0:
        break
    else:
        n+=1
        x.append(j)
def fun(k):
    if k==0:
        return 0
    if k==1:
        return 1
    if (k%2==0):
        return fun(k//2)
    if not(k%2==0):
        return (fun(k//2)+fun(k//2+1))
for l in range(0,len(x)):
    if x[l]%2==0:
        print(fun(x[l]-1))
    if not(x[l]%2)==0:
        print(fun(x[l]))

Edited by author 23.07.2015 23:40

I decided to write post my solution and comment it, may be it will
be useful for someone.
So, you have recursively defined sequence. Of course first idea is
to write recursive function. But, we need to find max element from
1 to n and if you will call function for every n in order to find
maximum element, such algorithm will cost O(n^2). Another way is to
store results gotten before in special array and compare gotten result
with max of them.
I hope I helped you at least as it.
And here is accepted solution in C++:
#include <iostream>

#define max(a, b) ((a) < (b) ? (b): (a))

int last = 1;
int mem[100000];
int max[100000];

int F(int n)
{
    for (int i = last+1; i <= n; ++i) {
        if (i%2)
            mem[i] = mem[i/2]+mem[i/2+1];
        else
            mem[i] = mem[i/2];

        max[i] = max(mem[i], max[i-1]);
    }

    return max[n];
}

int main()
{
    mem[0] = 0; mem[1] = 1;
    max[0] = 0; max[1] = 1;

    int n;
    while (1) {
        std::cin >> n;

        if (!n) break;

        std::cout << F(n) << std::endl;
    }


    return 0;
}

#include <stdio.h>
__int64 n, i, a[200002], b[200002], mx;
void solve(){
    a[1] = b[1] = mx = 1;
    for(i = 1 ; i < 100001 ; i ++){
       a[i << 1] = a[i];
       a[i << 1 | 1] = a[i] + a[i + 1];
       if(mx < a[i]) mx = a[i];
       b[i] = mx;
    }
    while(~scanf("%I64d", &n)){
       if(!n)  break;
       printf("%I64d ", b[n]);
    }
}
int main(){
    solve();
}

program p1079;
  var
    a:array[0..100000] of longint;
    m:array[1..100000] of longint;
    n,max,i:longint;
  begin
    max:=1;
    a[1]:=1;
    m[1]:=1;
    readln(n);
    while n<>0 do
      begin
        if n<=max then writeln(m[n])
          else
            begin
              for i:=max+1 to n do
                begin
                 if odd(i) then a[i]:=a[i div 2]+a[i div 2+1]
                   else a[i]:=a[i div 2];
                 if a[i]>=m[i-1] then m[i]:=a[i] else m[i]:=m[i-1];
                end;
            end;
        writeln(m[n]);
        readln(n);
      end;
  end.

a_10=a_5=a_2+a_3=a_1+a_1+a_2=1+1+1=3 Why it's 4?

Edited by author 01.06.2014 00:29