02/10/2018, 13:57
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ư ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | 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;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #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; } |
