Гайдо́ра та палички (Розбір)

Рішення

Оптимально побудувати за допомогою Трикутної конструкції, тобто ми продовжуємо додавати числа від $1$ до $m$, поки сума S \le x, ми знаємо, що сума перших $m$ цілих чисел є:

Зверніть увагу, що $T(m)$ зростає!, тому ми можемо виконати бінарний пошук на максимальному $m$, такому що T(m) \le m, з межами l=1 та r=2 \cdot 10^9, що буде безпечно, оскільки T(2 \cdot 10^9) > 2 \cdot 10^{18}, що є достатнім для вирішення задачі і також підходить для довгого типу 'long long' у C++.

Коли ми отримаємо $m$, ми приходимо до знаходження максимальної довжини палички, відповідь у цьому випадку буде максимальною з $m$ — найбільше ціле число, яке ми використовували в трикутній конструкції, та максимальною з залишкових цілих чисел. Формально

Складність \mathcal{O}(\log(2\cdot 10^9) \cdot t).

def T(n):return (n*(n+1))//2

def solve():
    n=int(input())
    l,r=1,2*10**9
    while(l<=r):
        m=(l+r)//2
        if(T(m)<n<T(m+1)):
            ans=m+1
            break
        if(T(m)==n):
            ans=m
            break
        if(T(m)<n):
            l=m+1
        if(T(m)>n):
            r=m-1
    if(T(ans)>n):ans-=1
    print(ans,max(ans,n-T(ans-1)))

for _ in range(int(input())):
    solve()