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 c++

$\color{#1fdb91}{\texttt{C}}\color{#0aaec9}{\texttt{+}}\color{#e9418e}{\texttt{+}}$

#include <bits/stdc++.h>

#define ll long long
#define N 100005

using namespace std;

ll t, n, a[N];

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    a[1] = 1;
    for (ll i=2; i<N; ++i) {
        if (i % 2 == 0) a[i] = a[i/2];
        else a[i] = a[i/2] + a[i/2+1];
    }
    
    for (ll i=1; i<N; ++i) a[i] = max(a[i-1], a[i]);
    
    cin >> t;
    while (t --> 0) {
        cin >> n;
        cout << a[n] << '\n';
    }
    
}

// Author : Daoanhviet96
// Language : C++

$\\$
\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}