هايدورا والعصي (شرح الحلول)

الحل

من الأمثل البناء باستخدام البناء المثلثي أي نستمر في جمع الأعداد من $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()