컨셉
주어진 정수 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입니다.
우리의 임무는 f(m) =l이 되도록 값 m을 결정하는 것입니다. 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
방법
순진한 접근 방식 사용 − 주어진 값, b, c에 대해 m의 모든 값에 대해 f(m)의 값을 찾아 비교합니다.
효율적인 접근 방식 사용 − 이진 검색을 구현하고 m =(min + max) / 2를 선택합니다. 여기서 min과 max는 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