Help Conan 12!

View as PDF
Submit solution
Points: 0.07 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
TIMUS
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 100000~. Mỗi dòng của ~T~ có ~1~ số ~N~ ~(N \leq 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.

Sample Input

2
5
10

Sample Output

3
4

Comments

Please read the guidelines before commenting.


  • 0
    vominhmanh10  commented on Dec. 4, 2025, 4:58 a.m.

    đọc ko kĩ đề đã mất 30p trừng con mắt :(

    import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
def f(n):
    if n == 0: return 0
    if a[n] != 0: return a[n]
    if n % 2 == 0:
        a[n] = f(n // 2)
        return a[n]
    else:
        a[n] = f(n // 2) + f(n // 2 + 1)
        return a[n]
pre = [0] * (10**5 + 5)
a = [0] * (10**5 + 5)
a[1] = 1
for i in range(10**5 + 5):
    f(i)
    pre[i] = max(pre[i - 1], a[i])
t = int(input())
while t:
    t -= 1
    n = int(input())
    print(pre[n])

  • -2
    quochung_ORZ  commented on June 19, 2025, 10:53 a.m.

    ez ez ez ez ez ez ez


  • -1
    kietjumper  commented on Nov. 10, 2024, 4:00 p.m. ← edited

    https://ideone.com/G4tPT4


  • -5
    Quangdpm  commented on Dec. 20, 2023, 11:11 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -67
    phanhuykhang  commented on June 15, 2021, 11:51 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.