MAXARR1 spoj – Help Conan 12 !

Nguồn đề bài: http://vn.spoj.com/problems/MAXARR1/

1. Đề bài MAXARR1 spoj

Năm ngoái Conan chỉ mới bước vào học Tin học thật sự. Thế nhưng anh ta bị đàn em là Như Quỳnh thách đố bài toán sau:

Cho T ≤ 100000. Mỗi dòng của T có 1 số N (N ≤ 100000). Dãy số A được xây dựng như sau:

• A[0] = 0
• A[1] = 1
• A[2i] = A[i]
• A[2i+1] = A[i] + A[i+1]

Nhiệm vụ của bạn là tìm số lớn nhất của dãy A từ 1 với N.

Input

Dòng đầu tiên là số T.

T dòng sau, mỗi dòng là 1 số N.

Output

Có T dòng tương ứng với giá trị lớn nhất của các đoạn.

Example

Input
2
5
10

Output
3
4

2. Thuật toán MAXARR1 spoj

Bài này không có gì để nói đến, dùng QHĐ bình thường thôi. Có thể vừa nhập vừa xử lí hoặc nhập xong rồi xử lí sau.

3. code tham khảo MAXARR1 spoj

Các bạn có thể tham khảo các cách viết sau

solution mẫu (2 code pascal, 1 code c++):

uses    math;
const   fi='';
        nmax=1000000;
type    data=longint;
var
        f:text;
        n:data;
        A,Amax:array[0..nmax+1] of word;

procedure xuli;
var     i:data;
begin
        for i:=1 to 500000 do
                begin
                        A[2*i]:=a[i];
                        amax[i*2]:=max(a[i*2],amax[i*2-1]);
                        a[2*i+1]:=a[i]+a[i+1];
                        amax[i*2+1]:=max(a[i*2+1],amax[i*2]);
                end;
end;


procedure docfile;
var     i,x:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);

        A[0]:=0;
        A[1]:=1;
        amax[0]:=0;
        amax[1]:=1;
        xuli;
        for i:=1 to n do
                begin
                        readln(f,x);
                        writeln(Amax[x]);
                end;
        close(f);
end;

begin
        docfile;
end.

+++

USES    math;
CONST   maxn = 100000;

VAR     t,i,j,m : longint;
        a,f : array[0..maxn] of int64;
        n : array[1..maxn] of longint;

BEGIN
        readln(t);
        m := 0;
        for i := 1 to t do begin
                readln(n[i]);
                m := max(n[i],m);
        end;
        a[0] := 0;
        a[1] := 1;
        for i := 1 to m div 2 do begin
                a[2*i] := a[i];
                a[2*i+1] := a[i] + a[i+1];
        end;
        f[1] := 1;
        for i := 2 to m do
                f[i] := max(f[i-1],a[i]);
        for i := 1 to t do
                writeln(f[n[i]]);
 END.

 c++

#include <stdio.h>
#include <algorithm>
using namespace std;

int a[100002],amax[100002];

void xuli()
{
    a[0]=amax[0]=0;
    a[1]=amax[1]=1;
    int i;
    for (i=1; i<=50000; i++)
    {
        a[i*2]=a[i];
        amax[i*2]=max(a[i*2],amax[i*2-1]);
        a[2*i+1]=a[i]+a[i+1];
        amax[2*i+1]=max(a[i*2+1],amax[i*2]);
    }
}

int main()
{
    int test;
    xuli();
    scanf("%d",&test);
    int i,x;
    for (i=1; i<=test; i++ )
    {
        scanf("%d",&x);
        printf("%dn",amax[x]);
    }
    return 0;
}