Help Conan 12!

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

admin

Dạng bài

Đ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
10

Output

3
4

Nguồn: vn.spoj

Bình luận

code này làm sao để AC vậy mn

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double 
#define str string
#define sst stringstream
#define ch char
#define st struct
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll T;
    cin >> T;
    vector<ll> q(T);
    ll nmax = 0;
    for (ll i = 0; i < T; ++i) {
        cin >> q[i];
        nmax = max(nmax, q[i]);
    }
    vector<ll> A(nmax + 1);
    A[0] = 0;
    if (nmax > 0) A[1] = 1;
    ll gtmax = 1;

    for (ll i = 2; i <= nmax; ++i) {
        if (i % 2 == 0) {
            A[i] = A[i / 2];
        }
        else {
            A[i] = A[i / 2] + A[i / 2 + 1];
        }
        gtmax = max(gtmax, A[i]);
    }
    for (ll i = 0; i < T; ++i) {
        cout << *max_element(A.begin(), A.begin() + q[i] + 1) << endl;
    }
    return 0;
}

-1

Phản hồi

3 bình luận nữa