मान लीजिए हमारे पास एक संख्या l और एक मोनोटोनिक बढ़ता हुआ अनुक्रम f(m) है, जहां f(m) = am + bm [log2(m)] + cm^3 और (a = 1, 2, 3, ...), (b = 1, 2, 3, ...), (c = 0, 1, 2, 3, ...)
यहां [log2(m)] आधार 2 का लॉग है और मान को नीचे की ओर पूर्णांकित करें। तो,
यदि m = 1, मान 0 है।
यदि m = 2-3, मान 1 है।
यदि m = 4-7, मान 2 है।
यदि m = 8-15, मान 3 है। और इसी तरह
हमें मान m ढूंढना है जैसे कि f(m) = l, यदि l अनुक्रम में मौजूद नहीं है तो हमें 0 प्रिंट करना होगा। हमें इस बात का ध्यान रखना है कि मान इस तरह से हैं कि उन्हें 64 बिट्स में दर्शाया जा सकता है और तीन पूर्णांक a, b और c 100 से कम या बराबर हैं।
तो, यदि इनपुट a = 2, b = 1, c = 1, l = 12168587437017 की तरह है, तो आउटपुट 23001 होगा क्योंकि f(23001) = 12168587437017।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
SMALLER_VAL := 1000000
LARGER_VAL := 1000000000000000
एक फ़ंक्शन solve() परिभाषित करें। यह a, b, c, n लेगा
ans := a * n
lg_val := n के आधार 2 के लॉग का फ्लोर
ans := ans + b * n * lg_val
ans := ans + c * n^3
ans वापस करें
मुख्य विधि से, निम्नलिखित करें -
begin := 1
end := SMALLER_VAL
यदि c, 0 के समान है, तो
end := LARGER_VAL
ans := 0
जब begin <= end, करें
mid := (begin + end) / 2 (केवल पूर्णांक भाग लें)
val := solve(a, b, c, mid)
यदि val, k के समान है, तो
ans := mid
लूप से बाहर निकलें
अन्यथा जब val > k, तो
end := mid - 1
अन्यथा,
begin := mid + 1
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
आउटपुट
23001
