ধারণা
একটি প্রদত্ত পূর্ণসংখ্যা 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 =(মিনিট + সর্বোচ্চ) / 2 নির্বাচন করুন যেখানে মিনিমাম এবং সর্বোচ্চকে m এর জন্য সম্ভাব্য সর্বনিম্ন এবং সর্বাধিক মান হিসাবে নির্দেশ করা হয়,
- যদি 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