5 sao đuy 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≤105 dòng. Mỗi dòng của T có 1 số N (N≤105). 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 với N. Dữ liệu vào Dòng đầu tiên là số T. T dòng sau, mỗi dòng là 1 số N. Kết quả Có T dòng tương ứng với giá trị lớn nhất của các đoạn. Sample Input 2 5 10 Sample Output 3 4
1 câu trả lời
#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[2*i] = a[i];
a[i*2 + 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';
}
}
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết giúp các em luyện tập và củng cố kiến thức hiệu quả
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 5 Địa 8 có lời giải chi tiết
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 4 Địa 8 có lời giải chi tiết
