MAXARR1 spoj - Help Conan 12 !

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

Nội dung bài viết

1. Đề bài MAXARR1 spoj
2. Thuật toán MAXARR1 spoj
3. code tham khảo MAXARR1 spoj

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 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;

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.

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;
}

#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;

}

MAXARR1 spoj – Help Conan 12 !

1. Đề bài MAXARR1 spoj

Input

Output

Example

2. Thuật toán MAXARR1 spoj

3. code tham khảo MAXARR1 spoj

Bài viết liên quan

One thought on “MAXARR1 spoj – Help Conan 12 !”

Trả lời Hủy