Nguồn đề bài: http://vn.spoj.com/problems/MAXARR1/
Nội dung bài viết
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++):
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. |
+++
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++
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; } |
Bài viết liên quan
- BLGEN spoj – Chuỗi gen đặc trưng
- MTTRAVEL spoj THPTCBT – Du lịch vòng quanh thế giới
- lời giải LATGACH spoj – Lát gạch
- BONUS spoj – VOI 2011 Phần thưởng
- MTHCN spoj – Hình chữ nhật kì lạ
- LIS spoj – Dãy con tăng dài nhất (bản khó)
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- MPILOT spoj – Pilots
- Đếm số Palindrome
- LNACS spoj – Dãy con chung không liền kề dài nhất
C++ nhớ dùng scanf vs printf nha! cin cout là k full đâu! <3