अवधारणा
किसी दिए गए पूर्णांक 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 पर ले जाने और मान को नीचे की ओर ले जाने का संकेत देता है। इसके परिणामस्वरूप,
अगर एम =1, मान 0 है।
अगर एम =2-3, मान 1 है।
अगर एम =4-7, मान 2 है।
अगर एम =8-15, मान 3 है।
हमारा कार्य m का मान इस प्रकार निर्धारित करना है कि f(m) =l, यदि l अनुक्रम से संबंधित नहीं है तो हमें 0 प्रिंट करना होगा।
यह ध्यान दिया जाना चाहिए कि मान इस तरह से हैं कि उन्हें 64 बिट्स में दर्शाया जा सकता है और तीन पूर्णांक ए, बी और सी 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) के मान ज्ञात कीजिए और इसकी तुलना कीजिए।
कुशल दृष्टिकोण का उपयोग करना - बाइनरी सर्च को लागू करें, एम =(न्यूनतम + अधिकतम) / 2 चुनें जहां न्यूनतम और अधिकतम को एम के लिए संभव न्यूनतम और अधिकतम मान के रूप में दर्शाया गया हो,
- यदि f(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;
// Shows function to return the value of f(m) for given values of a,
b, c, 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;
// Now if c is 0, then value of m can be in order of 10^15.
// Now if c1!=0, then m^3 value has to be in order of 10^18
// so maximum value of m can be 10^6.
if (c1 == 0) {
end1 = LARGE_N;
}
long long ans1 = 0;
// Now for efficient searching, implement binary search.
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;
}
// Driver code
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