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
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';
}
}
2 bình luận nữa