Help Conan 12!
Xem PDF
Điểm:
1100 (p)
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
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 \leq 10^5\) dòng. Mỗi dòng của \(T\) có \(1\) số \(N\) (\(N \leq 10^5\)).
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]\)
Yêu cầu: Nhiệm vụ của bạn là tìm số lớn nhất của dãy \(A\) từ \(1\) tớ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
Test 1
Input
2
5
10Output
3
4Nguồn: vn.spoj
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
bài này dùng mảng tiền tố đc mà ta, sao trong dạng bài chỉ có dp nhỉ
include <iostream>
using namespace std;
const int maxn = 1e5;
define ll long long
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll a[maxn + 1],f[maxn + 1];
a[0] = 0;
a[1] = 1;
f[0] = 0;
ll i;
for (i = 1;i <= maxn/2;i++)
{
a[2i] = a[i];
a[i2 + 1] = a[i] + a[i+1];
}
for (i = 1;i <= maxn;i++)
f[i] = max(f[i-1],a[i]);
int t;cin >> t;
while (t--)
{
int n;cin >> n;
cout << f[n] << '\n';
}
}