Khái niệm
Đối với một số nguyên l cho trước và một dãy tăng đơn điệu -
f (m) =am + bm [log2 (m)] + cm ^ 3 trong đó (a =1, 2, 3,…), (b =1, 2, 3,…), (c =0, 1, 2, 3,…) Hãy nhớ rằng, ở đây, [log2 (m)] cho biết, lấy bản ghi về cơ số 2 và làm tròn giá trị xuống. Như kết quả của điều này,
nếu m =1, giá trị là 0.
nếu m =2-3, giá trị là 1.
nếu m =4-7, giá trị là 2.
nếu m =8-15, giá trị là 3.
Nhiệm vụ của chúng ta là xác định giá trị m sao cho f (m) =l, nếu l không thuộc dãy thì chúng ta sẽ in ra 0.
Cần lưu ý rằng các giá trị theo cách mà chúng có thể được biểu diễn bằng 64 bit và ba số nguyên a, b và c không vượt quá 100.
Đầu vào
a = 2, b = 1, c = 1, l = 12168587437017
Đầu ra
23001 f(23001) = 12168587437017
Đầu vào
a = 7, b = 3, c = 0, l = 119753085330
Đầu ra
1234567890
Phương thức
Sử dụng phương pháp tiếp cận ngây thơ - Với các giá trị a, b, c đã cho, hãy tìm các giá trị của f (m) với mọi giá trị của m rồi so sánh.
Sử dụng phương pháp tiếp cận hiệu quả - Triển khai Tìm kiếm nhị phân, chọn m =(min + max) / 2 trong đó min và max được chỉ ra là giá trị nhỏ nhất và lớn nhất có thể cho m khi đó,
- Nếu f (m)
- Nếu f (m)> l thì giảm m.
- Nếu f (m) =l thì m là câu trả lời bắt buộc.
- Bây giờ, hãy lặp lại các bước trên cho đến khi và trừ khi tìm thấy giá trị bắt buộc hoặc không thể thực hiện được trong trình tự.
Ví dụ
// 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;
} Đầu ra
23001 1234567890 0