পাইথনে মনোটোনিক সিকোয়েন্সে উপাদানের পজিশন বের করা

ধরা যাক একটি সংখ্যা l এবং একটি মনোটোনিক ইনক্রিজিং সিকোয়েন্স f(m) দেওয়া আছে, যেখানে f(m) = a*m + b*m*[log2(m)] + c*m^3। এখানে a,b,c পজিটিভ ইন্টিজার (a,b ≤ 100, c ≤ 100)। [log2(m)] মানে লগ বেস ২ ফ্লোর ভ্যালু। আমাদের m বের করতে হবে যাতে f(m) = l। না থাকলে 0 প্রিন্ট করুন।

ইনপুট: a=2, b=1, c=1, l=12168587437017 → আউটপুট 23001।

সমাধানের ধাপসমূহ (বাইনারি সার্চ)

SMALLER_VAL=10^6, LARGER_VAL=10^15
solve(a,b,c,n): return a*n + b*n*floor(log2(n)) + c*n^3
begin=1, end=SMALLER_VAL; যদি c==0: end=LARGER_VAL
while begin <= end:
- mid = (begin+end)//2; val = solve(a,b,c,mid)
- যদি val==k: ans=mid; break
- যদি val>k: end=mid-1 else: begin=mid+1
return ans

উদাহরণ

from math import log2, floor
SMALLER_VAL = 1000000
LARGER_VAL = 1000000000000000
def solve(a, b, c, n):
    ans = a * n
    lg_val = floor(log2(n))
    ans += b * n * lg_val
    ans += c * n**3
    return ans
def get_pos(a, b, c, k):
    begin = 1; end = SMALLER_VAL
    if c == 0: end = LARGER_VAL
    ans = 0
    while begin <= end:
        mid = (begin + end) // 2
        val = solve(a, b, c, mid)
        if val == k:
            ans = mid
            break
        elif val > k:
            end = mid - 1
        else:
            begin = mid + 1
    return ans
a = 2; b = 1; c = 1; k = 12168587437017
print(get_pos(a, b, c, k))

ইনপুট

2,1,1,12168587437017