কনসেপ্ট
একটি পূর্ণসংখ্যা l এবং মনোটোনিক বৃদ্ধিমান সিকোয়েন্স f(m) = a*m + b*m*floor(log2(m)) + c*m³ দেওয়া আছে (a,b,c ≤ 100)। f(m) = l হলে m খুঁজে বের করুন। না পেলে 0 ফেরত দিন। ৬৪-বিট ইন্টিজার রেঞ্জ।
ইনপুট ১
a=2, b=1, c=1, l=12168587437017
আউটপুট ১
23001
ইনপুট ২
a=7, b=3, c=0, l=119753085330
আউটপুট ২
1234567890
পদ্ধতি
দক্ষ পদ্ধতি (বাইনারি সার্চ): f(m) একদম ক্রমবর্ধমান। low=1, high=10⁶ (c!=0 হলে) বা 10¹⁵ (c=0 হলে)। mid=(low+high)/2। f(mid) < l হলে low=mid+1, > l হলে high=mid-1, = l হলে mid ফেরত দিন।
উদাহরণ (C++ কোড)
// C++: মনোটোনিক সিকোয়েন্সে বাইনারি সার্চ
#include <iostream> #include <math.h>
#define SMALL_N 1000000
#define LARGE_N 1000000000000000
using namespace std;
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;
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() {
cout << getPositionInSeries1(2,1,1,12168587437017) << endl;
cout << getPositionInSeries1(7,3,0,119753085330) << endl;
cout << getPositionInSeries1(6,2,1,11975309533) << endl;
return 0;
}
আউটপুট
23001 1234567890 0
