Algorithm
Right now she actually isn't. But she will be, if you don't solve this problem.
You are given integers n, k, A and B. There is a number x, which is initially equal to n. You are allowed to perform two types of operations:
- Subtract 1 from x. This operation costs you A coins.
- Divide x by k. Can be performed only if x is divisible by k. This operation costs you B coins.
The first line contains a single integer n (1 ≤ n ≤ 2·109).
The second line contains a single integer k (1 ≤ k ≤ 2·109).
The third line contains a single integer A (1 ≤ A ≤ 2·109).
The fourth line contains a single integer B (1 ≤ B ≤ 2·109).
Output a single integer — the minimum amount of coins you have to pay to make x equal to 1.
9
2
3
1
6
5
5
2
20
8
19
3
4
2
12
In the first testcase, the optimal strategy is as follows:
- Subtract 1 from x (9 → 8) paying 3 coins.
- Divide x by 2 (8 → 4) paying 1 coin.
- Divide x by 2 (4 → 2) paying 1 coin.
- Divide x by 2 (2 → 1) paying 1 coin.
The total cost is 6 coins.
In the second test case the optimal strategy is to subtract 1 from x 4 times paying 8 coins in total.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
long long n, k, A, B;
long long rec(long long x) {
if(x <= 0)
return 2e18;
if(x == 1)
return 0;
long long tmp = x - (k * (x / k));
if(k > x)
return (x - 1) * A;
if(x % k == 0) {
if((x - (x / k)) * A < B)
return rec(x / k) + (x - (x / k)) * A;
else
return rec(x / k) + B;
} else
return rec(x - tmp) + (tmp * A);
}
int main() {
cin >> n >> k >> A >> B;
if(k == 1 || k > n) {
cout << (n - 1) * A << endl;
return 0;
}
if(k == n) {
cout << min(B, (n - 1) * A) << endl;
return 0;
}
cout << rec(n) << endl;
return 0;
}Input
2
3
1
Output
Demonstration
Codeforces Solution-Our Tanya is Crying Out Loud-Solution in C, C++, Java, Python