अवधारणा
एक दिए गए पूर्णांक l और एक मोनोटोनिक बढ़ते अनुक्रम के संबंध में −
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
इनपुट
a = 7, b = 3, c = 0, l = 119753085330
आउटपुट
1234567890
विधियां
भोले दृष्टिकोण का उपयोग करके − दिए गए a, b, c के मानों के संबंध में, m के हर मान के लिए f(m) के मान ढूंढें और तुलना करें।
कुशल दृष्टिकोण का उपयोग करके − बाइनरी खोज लागू करें, m = (min + max) / 2 चुनें जहां min और max को m के लिए संभव न्यूनतम और अधिकतम मानों के रूप में इंगित किया जाता है, तब,
<उल क्लास="सूची"><ली>यदि f(m) < l तो m बढ़ाएं।<ली>यदि f(m) > l तो m घटाएं।<ली>यदि f(m) = l तो m आवश्यक उत्तर है।<ली>अब उपरोक्त चरणों को तब तक दोहराएं जब तक आवश्यक मान न मिल जाए या यह अनुक्रम में संभव न हो।उदाहरण
<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// C++ implementation of the approach #include <iostream> #include <math.h> #define SMALL_N 1000000 #define LARGE_N 1000000000000000 using namespace std; // दिए गए a, b, c, m मानों के लिए f(m) का मान लौटाने वाला फ़ंक्शन long long func(long long a1, long long b1, long long c1, long long m){ long long res1 = a1 * m; long long logVlaue1 = floor(log2(m)); res1 += b1 * m * logVlaue1; res1 += c1 * (m * m * m); return res1; } long long getPositionInSeries1(long long a1, long long b1, long long c1, long long l){ long long start1 = 1, end1 = SMALL_N; // अब यदि c 0 है, तो m का मान 10^15 के क्रम में हो सकता है। // अब यदि c1!=0, तो m^3 मान 10^18 के क्रम में होना चाहिए // तो m का अधिकतम मान 10^6 हो सकता है। if (c1 == 0) { end1 = LARGE_N; } long long ans1 = 0; // अब कुशल खोज के लिए, बाइनरी खोज लागू करें। while (start1 <= end1) { long long mid1 = (start1 + end1) / 2; long long val1 = func(a1, b1, c1, mid1); if (val1 == l) { ans1 = mid1; break; } else if (val1 > l) { end1 = mid1 - 1; } else { start1 = mid1 + 1; } } return ans1; } // ड्राइवर कोड int main(){ long long a1 = 2, b1 = 1, c1 = 1; long long l = 12168587437017; cout << getPositionInSeries1(a1, b1, c1, l)<<endl; long long a2 = 7, b2 = 3, c2 = 0; long long l1 = 119753085330; cout << getPositionInSeries1(a2, b2, c2, l1)<<endl; long long a3 = 6, b3 = 2, c3 = 1; long long l2 = 11975309533; cout << getPositionInSeries1(a3, b3, c3, l2)<<endl; return 0; }आउटपुट
23001 1234567890 0
