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\)\(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\) 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

  • \(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
10
Output
3
4

Nguồn: vn.spoj


Bình luận


  • 0
    2009_Kiet 1:43 p.m. 31 Tháng 8, 2023

    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[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';
    }
    }