Editorial for Help Conan 12!


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const maxn=100000;
var a:array[0..maxn] of longint;
    m:array[0..maxn] of longint;
    n,t,i:longint;

procedure init;
var i,max:longint;
begin
     a[0]:=0; a[1]:=1; m[0]:=0; m[1]:=1;
     max:=1;
     for i:=2 to maxn do
     begin
          a[i]:=a[i div 2];
          if i mod 2 = 1 then a[i]:=a[i]+a[i div 2 + 1];
          if a[i]>max then max:=a[i];
          m[i]:=max;
     end;
end;

begin
     init;
     readln(t);
     for i:=1 to t do
     begin
          readln(n);
          writeln(m[n]);
     end;
end.

Code mẫu của happyboy99x

#include <cstdio>

int f[100000+5];
int m[100000+5];

int main() {
    f[1] = 1; m[1] = 1;
    for( int i = 2; i <= 100000; ++i ) {
        f[i] = f[i/2] + (i%2)*f[i/2+1];
        m[i] = f[i] > m[i-1] ? f[i] : m[i-1];
    }
    int t; scanf( "%d", &t );
    while(t--) {
        int n; scanf( "%d", &n );
        printf( "%d\n", m[n] );
        //printf( "%d\n", n ? f[n] > f[n-1] ? f[n] : f[n-1] : 0 );
    }
    return 0;
}

Code mẫu của ladpro98

program maxarr1;
uses    math;
const   fi='';
var     a,maxA:array[0..100001] of longint;
        inp:text;
        lenA:longint;

procedure init0;
begin
        lenA:=1;
        a[0]:=0;
        a[1]:=1;
        maxA[0]:=0;
        maxA[1]:=1;
end;

procedure initA(n:longint);
var     i:longint;
begin
        if n<=lenA then exit;

        for i:=lenA+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];
                maxA[i]:=max(maxA[i-1],a[i]);
        end;
        lenA:=n;
end;

procedure process;
var     t,i,n:longint;
begin
        readln(inp,t);
        for i:=1 to t do
        begin
                readln(inp,n);
                initA(n);
                writeln(maxA[n]);
        end;
end;

procedure openFile;
begin
        assign(inp,fi);
        reset(inp);

end;

procedure closeFile;
begin
        close(inp);
end;

begin
        openFile;
        init0;
        process;
        closeFile;
end.

Code mẫu của RR

uses math;
var
  a:array[0..100111] of longint;
  n,test:longint;
begin
  a[0]:=0;
  a[1]:=1;
  for n:=2 to 100000 do
    if n and 1=0 then a[n]:=a[n shr 1]
    else a[n]:=a[n shr 1]+a[n shr 1+1];

  for n:=1 to 100000 do
    a[n]:=max(a[n],a[n-1]);

  read(test);
  for test:=1 to test do
    begin
      read(n);
      writeln(a[n]);
    end;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
long n,T,a[100001],F[100001];
a[0]=0;a[1]=1;
for(long i=0;i<=100000;i++)
  {
  if(i%2==0)
    a[i]=a[i/2];
  else
    a[i]=a[i/2]+a[i/2+1];
  }
F[0]=0;  
for(long i=0;i<=100000;i++)
  {
  if(a[i]>F[i-1])
    F[i]=a[i];
  else F[i]=F[i-1];
  }
scanf("%ld",&T);
for(long i=1;i<=T;i++)
  {
  scanf("%ld",&n);
  printf("%ld\n",F[n]);
  }
//getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program MAXARR11;
Const
  input  = '';
  output = '';
  maxn = 100000;
Var
  F,max: array[0..maxn] of integer;
  n,t: integer;
  fi,fo: text;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure solve;
Var
  i: integer;
Begin
  F[0]:= 0;
  F[1]:= 1;

  For i:= 2 to maxn do
    if odd(i) then F[i]:= F[i shr 1] + F[i shr 1 + 1]
              else F[i]:= F[i shr 1];

  max[0]:= 0;
  For i:= 1 to maxn do
    if F[i] > max[i - 1] then max[i]:= F[i] else max[i]:= max[i - 1];
End;

Procedure printresult;
Var
  i: integer;
Begin
  Readln(fi, t);
  For i:= 1 to t do
    Begin
      Readln(fi, n);
      Writeln(fo, max[n]);
    End;
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  openfile;
  solve;
  printresult;
  closefile;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   100011
typedef unsigned long long ull;
ull val[MAX];
ull max[MAX];
long n,t,c;
void init(void)
{
     long i;
     val[0]=0;
     val[1]=1;
     max[0]=0;
     max[1]=1;
     for (i=2;i<=MAX-5;i=i+1)
         {
          if (i%2==0) val[i]=val[i/2];
          else val[i]=val[i/2]+val[i/2+1];
          if (max[i-1]<val[i]) max[i]=val[i];
          else max[i]=max[i-1];
         }
}
int main(void)
{
    init();
    scanf("%ld",&t);
    for (c=1;c<=t;c=c+1)
        {
         scanf("%ld",&n);
         printf("%ld\n",max[n]);
        }
}

Code mẫu của khuc_tuan

#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define Lap(i,n) for(int i=1;i<=(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define Fit(i,v) for(__typeof(v.begin()) i=v.begin();i!=v.end();++i)
#define Fill(a,b) memset((a), (b), sizeof(a))
#define pb push_back
#define MP make_pair
#define pause system("pause");

typedef long long LL;

#define MAX 100000

int m[MAX+1], a[MAX+1];

int main() {
    int t;
    scanf("%d", &t);
    a[0] = 0;
    a[1] = 1;
    Lap(i,MAX) a[i] = (i%2) ? (a[i/2]+a[i/2+1]) : a[i/2];
    m[0] = 0;
    Lap(i,MAX) m[i] = max(m[i-1],a[i]);
    Lap(tt,t) {
        int n;
        scanf("%d", &n);
        printf("%d\n", m[n]);
    }
    //pause 
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.