Right now she actually isn't. But she will be, if you don't solve this problem. You are…
- User
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.
What is the minimum amount of coins you have to pay to make x equal to 1? Input
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
Output a single integer — the minimum amount of coins you have to pay to make x equal to 1.
Examples
Input
9 2 3 1
Output
6
Input
5 5 2 20
Output
8
Input
19 3 4 2
Output
12
Note
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.
Assistant
We need to compute minimum cost to reduce n to 1 using operations: subtract 1 (cost A) and divide by k if divisible (cost B). This is a classic problem (like Codeforces 1373B? Actually it's from Codeforces "A and B and Interesting Substrings"? No, it's "A and B and Team Training"? Not that. This problem is known: given n,k,A,B, minimize cost to reduce to 1. It's often solved by greedy: while x>1, consider whether to subtract until divisible or do some other steps. But note constraints up to 2e9, so we need an efficient algorithm, perhaps O(log n) or similar.
Observations: Division by k is beneficial if it saves cost compared to subtracting down to the next multiple etc. But careful: If k=1, division is useless (since dividing by 1 does nothing, but input says k can be 1, but division only allowed if x divisible by 1 (always true) but dividing by 1 does not change x; that would be infinite loop. However constraints: "Divide x by k. Can be performed only if x is divisible by k." For k=1, dividing would always be possible but doesn't change x, so it's never useful. So we must treat k=1 specially: Only subtracts allowed, cost = (n-1)*A. So we can handle separately.
Otherwise, k>=2. Then division reduces x quickly. However, sometimes it's cheaper to subtract all the way rather than pay B for division if A is very cheap and B very expensive.
Let's think about dynamic programming? n up to 2e9, can't do DP. We need to compute minimal cost from n to 1. Since operations are subtract 1 and divide by k (when divisible). This is reminiscent of reducing to 0 or 1 with given costs. But we can think backwards: starting from 1, we can multiply by k (reverse of division) or add 1 (reverse of subtract). But maybe easier to go forward from n.
Consider greedy approach: While x>1, if x%k==0, we have a decision: either divide (cost B) or perhaps subtract some and then divide later. If not divisible, we could subtract until divisible, or subtract all the way to 1. So typical solution: For each step, we consider: if x<k, we just subtract to 1. Otherwise, we can compute cost to reduce x to 1 as: let r = x mod k. Then we can subtract r times to make x divisible (cost r*A), then divide (cost B). Then we have new x = (x - r)/k = floor(x/k). But maybe it's cheaper to subtract more than r, i.e., not divide at that point, perhaps subtract all the way? But we can compare cost of dividing vs subtracting all the way.
Specifically, at a given x, the cost to go from x to floor(x/k) via subtract r and divide is r*A + B. Alternatively, we could subtract all the way to 1: cost = (x-1)A. But we might also consider doing multiple subtracts before dividing? But if we subtract more than r, we get to some number y which is divisible by k? Actually if we subtract s > r, then we get to x-s which may still be divisible? Actually if x%k = r, then x-s mod k = (r - s) mod k. For it to be divisible by k, we need s ≡ r (mod k). The smallest positive s such that x-s divisible is s = r (as r < k). Larger s would be r + tk for t>=1. So we could subtract r + k to get to x - (r+k) which is also divisible by k (since (r+k) ≡ r mod k). That would be more subtracts, then we could divide. But is that ever beneficial? Possibly if B is very expensive and A very cheap, but dividing later yields smaller number? Let's see: Suppose we subtract r+k (cost (r+k)*A) then divide (cost B) to get to (x - (r+k))/k = floor(x/k) - 1. That yields a smaller number than directly dividing after r subtracts. But maybe it's better to subtract more and then divide to a smaller number, avoiding some future operations? However, we could also just divide at the current step then subtract some later. Which is more cost effective? We need to consider the overall plan.
We can think recursively: define f(x) minimal cost to reduce x to 1. For x>1:
If x%k == 0: we can either divide: f(x/k) + B, or subtract 1 then consider: but subtract 1 would make x not divisible, so it's like we could choose to not divide now. So we need to compare dividing with subtracting until we get to a point where dividing is cheaper? Actually we can consider that the optimal strategy might sometimes not divide even when divisible, if dividing leads to a high cost later (but we can still compute recursively). However, for large x, division is generally beneficial. But we need an efficient method.
Let’s analyze the problem more systematically.
We can consider two operations: -1 and /k (when divisible). This is similar to computing minimal cost to reduce n to 1, which can be solved by a greedy: at each step, if k divides x, compare cost of division vs subtracting all the way from x to 1. But also consider the possibility of subtracting some multiples to skip division at that level.
Actually known Codeforces problem: "Minimum number of coins to reduce n to 1" with operations: subtract 1 cost a, divide by k cost b if divisible. I recall editorial: While n >= k, we take remainder r = n%k, subtract r, pay r*a, then possibly divide if b is cheap. But wait, there is a nuance: sometimes it's cheaper to subtract more than remainder to avoid a division if b is large. But also when we subtract to make divisible, then divide. But after division, we might subtract again, etc. The known solution is: If k=1: output (n-1)*a. Else, let ans=0. While n>1: if n%k==0: we can consider whether it's cheaper to subtract all the way: compare (n - n/k)*a? Hmm.
Let's simulate: suppose n=9, k=2, A=3, B=1. At n=9, remainder r=1. So subtract 1 (cost 3) to get 8, then divide cost 1 to get 4: total 4 so far. At n=4, divisible, r=0. Should we divide? Divide cost 1 to get 2. At 2, divide cost 1 to get 1. Total 6.
Now consider alternative: At 9, what if we subtract 3 to get 6 (divisible by 2? 6%2=0, so after subtracting 3 we could divide? 9-3=6, subtract cost 9, then divide cost 1 => 10 total, not good. So optimal uses minimal r.
But what about a case where A is tiny and B huge? For example, n=100, k=10, A=1, B=1000. The best is subtract 99 to 1 cost 99. Dividing: At 100, divisible, but division cost 1000, then we get 10, still need to reduce 10 to 1. At 10, division cost 1000 again (if we divide) to get 1 cost 2000, or subtract 9 cost 9, total 1009. So subtracting all the way is cheaper. So we need to compare: At each step when divisible, we need to decide whether to divide or just subtract all the way. However, what about intermediate steps: suppose n=100, k=10, A=1, B=15. Dividing at 100: cost 15, then we have 10. From 10, we could divide again (cost 15) to get 1 -> total 30; or subtract 9 from 10 cost 9 -> total 24; So total 24. Subtract all the way: 99. So dividing is better. But note: from 100, if we subtract to 90? That would cost 10, then divide cost 15 to get 9, then subtract 8 cost 8 -> total 33, worse.
Thus the optimal strategy seems to be: while n >= k, we compute remainder r = n % k. We have two options: (i) subtract r to make n divisible, then divide (if that is beneficial) OR (ii) just subtract all the way to 1 (i.e., stop dividing). But we also have the option to subtract more than r to get to a lower multiple? That could be considered as part of subtracting all the way eventually.
Wait, what if n is large, k is large but A is small, B is moderate. Maybe we want to subtract down to a point where dividing is cheaper overall? But we can incorporate that by considering that when we decide to divide, we want to do it at the largest possible multiple? Actually the structure of optimal solution: The division operation is most beneficial when we can reduce the number significantly. Since subtracts are linear, it's usually optimal to use division whenever it reduces the number enough that the cost of subtracts to get to a divisible state plus division cost is less than subtracting all the way from current n to the target number after division times? Let's think recursively.
Define f(n) = minimum cost from n to 1. For n>1:
If n%k != 0: we cannot divide immediately. We could subtract 1 repeatedly until we either reach 1 or reach a multiple of k. So we have two choices: either subtract all the way to 1: cost (n-1)A; or subtract until we get to the next lower multiple of k, then consider dividing. So let r = n % k. Then we can subtract r (cost rA) to reach m = n - r, which is divisible by k. Then we have to decide whether to divide m or maybe subtract more? But m is divisible, so from m we have options: either divide (cost B) to get m/k, then continue with f(m/k); or subtract further? Subtracting further from m would mean subtract some amount to get to another multiple? That would be subtractions of multiples of k? But if we subtract 1 from m, we lose divisibility. That might be part of an alternative path that avoids dividing at m. So from n, after subtracting r to reach m, we have the choice between: (i) proceed with f(m) (which includes the possibility of dividing or not), or (ii) subtract further. But we have already accounted for subtracting all the way from n: cost (n-1)A = rA + (m-1)A? Actually (n-1) = r + (m-1). So subtracting all the way from n includes subtracting r then continuing subtracting from m down to 1. So that's essentially same as: after subtracting r, we could decide to not divide and just subtract all the way from m. So f(m) would be less or equal to (m-1)A? Actually f(m) is the minimal cost from m to 1, which could be less than (m-1)A if division helps. So after subtracting r, we have to evaluate f(m). But we cannot simply say f(n) = min( (n-1)A, rA + B + f(m/k) )? Because from n we could also subtract r, then divide (cost B), then f(m/k). That's one candidate. And we could also subtract r, then maybe not divide, but f(m) might involve division later. But note: f(m) is minimal cost from m to 1. That cost can be achieved without the subtraction of r because we are already at m. However, from n we have already spent rA to get to m. So another candidate is rA + f(m). But is that always considered? Compare rA + f(m) to (n-1)A = rA + (m-1)A. Since f(m) <= (m-1)A, the candidate rA + f(m) is at least as good as (n-1)A? Actually rA + f(m) <= rA + (m-1)A = (n-1)A. So it's always at least as good as subtracting all the way? Not exactly because f(m) might use division, which could be cheaper than subtracting. So indeed we should consider rA + f(m) as a candidate, not just (n-1)A. But is it possible that the optimal path from n does not involve subtracting exactly r to reach the next lower multiple? Could it be optimal to subtract more than r to reach a lower multiple, then divide? That would mean we subtract s where s > r and s ≡ r mod k, so that n-s is divisible. Let s = r + tk, t>=1. Then cost = sA + B to get to (n-s)/k = floor(n/k) - t. Then we continue from that number. Could that be better than subtracting r and then dividing? Possibly if division is costly, but we might want to divide to a smaller number to reduce subsequent subtracts? But dividing to a smaller number means we do more subtracts before division (s larger) and then division yields a smaller number, which may require fewer subsequent operations. However, we could also achieve similar effect by dividing after r subtracts and then doing subtracts later. Let's compare two strategies:
Strategy 1: subtract r, divide (cost rA + B) to get n1 = floor(n/k). Then we might subtract some amount later to reach next division, etc.
Strategy 2: subtract s = r + k, divide (cost (r+k)A + B) to get n2 = floor(n/k) - 1. Now from n2, we need to reduce to 1.
Alternative: After Strategy 1, from n1 we could subtract something. In fact, we could simulate: after dividing to n1, we might decide to subtract some amount to get to a multiple for next division. But from n2, we have a smaller number; the total remaining cost f(n2) might be less than f(n1) + something? Let's think: Could there be a situation where it's cheaper to subtract extra before division rather than after division? Because subtract costs A per unit. In both cases, the total number of subtract operations to reduce n to some target is the same if we consider the net effect? Let's examine: The operations are not commutative. For a given sequence, the total number of subtracts and divides can be counted. For a given n, suppose we want to apply a division at some point when the number becomes m, which is divisible by k. To get from n to m, we subtract (n-m) (cost (n-m)*A). Then divide cost B, then continue. The resulting number after division is m/k. So total cost to go from n to m/k is (n-m)A + B. The alternative: If we instead subtract more before dividing, we get a smaller m, then division yields even smaller. But could we achieve the same final number by dividing first then subtracting? Not exactly, because division reduces by factor k, so subtract after division costs less subtracts for the same reduction? Let's compare:
Option A: Subtract (n - m) to get m (divisible), divide to m/k. Option B: Subtract (n - m') to get m' (divisible), where m' < m, divide to m'/k.
Now consider achieving a particular target T after division and further steps. Could Option B be cheaper? Possibly if B is expensive and we want to avoid multiple divisions. But perhaps the optimal strategy is to always divide as early as possible (i.e., at the highest possible multiple) if division is cheap relative to subtracts? Or always at the lowest multiple? Let's attempt to derive optimal policy.
We can consider this as a shortest path problem on numbers from n down to 1, with edges: x -> x-1 cost A, and if x%k==0, x -> x/k cost B. Since n is large, we need to exploit structure.
One approach: use Dijkstra? Not feasible.
Another approach: This is similar to reducing n to 1 by either subtracting 1 or dividing by k. This is like computing minimal cost, which can be done greedily by considering that division is beneficial when B is relatively small compared to A * (something). Often the solution is:
if k == 1: print (n-1)A. else: ans = 0 while n > 1: if n < k: ans += (n-1)A break r = n % k if r == 0: # compare cost of dividing vs subtract all the way? # Actually we need to decide whether to divide or subtract some? # At this point, n divisible by k. # If dividing is cheaper than subtracting (n - n/k) (which is the amount we would subtract if we wanted to go from n to n/k without division), then divide. # But we might also consider not dividing at this n and subtract 1 to then maybe divide later? That seems suboptimal because subtracting 1 from a multiple makes it non-multiple, then later we might need to subtract more to become multiple again, essentially paying more subtracts. Typically if n is divisible, it's best to either divide now or subtract all the way to 1. Because if we subtract 1, we lose divisibility and then later we'll have to subtract again to become divisible, which would be at least as many subtracts as if we had just divided now? Actually it's complicated. Let's examine: Suppose n divisible by k. If we divide now, we pay B and go to n/k. If we subtract 1, we go to n-1, which is not divisible; to later divide we would need to subtract ( (n-1) % k )? Actually (n-1) mod k = k-1, so to make it divisible we need to subtract k-1 more (or subtract until reaching next lower multiple). So total subtracts to get to a divisible number from n-1 would be (k-1) to get to n-k? Wait n-1 subtract (k-1) gives n-k, which is divisible. Then we could divide. So subtract path: subtract 1 (cost A), then subtract (k-1) (cost (k-1)A) to get to n-k, then divide (cost B) to get (n-k)/k = n/k - 1. That total cost = kA + B, and resulting number is n/k - 1. In contrast, dividing immediately yields n/k with cost B. Then from n/k we could subtract 1 cost A to reach n/k - 1 if needed. So immediate division + optional subtract gives total = B + A to reach n/k - 1. So comparing: immediate division + one subtract = B + A. Delaying division by subtracting 1 first yields cost = kA + B to reach n/k - 1. Since k>=2, k*A >= 2A, so immediate division is always cheaper if we want to get to the same number. So it's never optimal to subtract from a divisible state unless we plan to never divide that number (i.e., subtract all the way to 1). Because any subtraction from a divisible state before division just increases total subtract cost and delays division, leading to same target later but with higher cost. Thus, at a divisible n, the optimal decision is either divide now (and then continue), or start subtracting all the way to 1 (i.e., never use division again from this point). There's no point to subtract some then later divide from a lower multiple, as that would be more expensive than dividing now and then subtracting later to the same eventual number.
Thus, for n divisible by k, we compare:
- Option divide: cost = B + f(n/k).
- Option not divide: cost = (n-1)*A (since we would just subtract all the way). But we might also consider not dividing now but dividing later after some subtracts? That would be as argued worse than dividing now. So we can safely consider only these two.
Now for n not divisible by k, we need to make it divisible if we ever want to divide. Since subtraction is the only way to reduce n until it becomes divisible. So we could either subtract all the way to 1 (cost (n-1)*A) or subtract enough to reach the next lower multiple of k (which is n - r, where r = n%k) and then from that multiple, we have the same decision: either divide or subtract all the way. But as argued, from that multiple, the optimal is either divide or subtract all the way. So we can define:
Let r = n % k. Let m = n - r (the largest multiple of k less than n). Then options:
- Subtract all the way: cost = (n-1)*A.
- Subtract r to get m, then decide at m: either (i) divide, or (ii) subtract all the way from m. But as we said, at m we should choose the better between dividing and subtracting all the way.
So candidate costs:
- Cost_sub_all = (n-1)*A.
- Cost_sub_to_m + cost_from_m, where cost_from_m = min( (m-1)*A, B + f(m/k) )? Actually careful: cost_from_m = f(m) because m is a state, and f(m) is the minimal cost from m to 1. But we can evaluate f(m) recursively. However, we can also combine: subtract r to m (cost rA) then if we decide to subtract all the way from m: total cost = rA + (m-1)*A = (n-1)*A, which is same as cost_sub_all. So that candidate is redundant. The new candidate is subtract r then divide: cost = rA + B + f(m/k). So effectively f(n) = min( (n-1)*A, rA + B + f(m/k) ). But is that complete? Could there be a case where we subtract more than r to a lower multiple? As argued, subtracting extra before dividing seems suboptimal compared to dividing earlier? But let's test with an example.
Suppose n=10, k=3, A=1, B=10. n%3=1, r=1, m=9. Options:
- Subtract all the way: cost 9.
- Subtract 1 to get 9 (cost1), then from 9 (divisible) we have two options: divide (cost10) to get 3, then f(3) from 3; or subtract all from 9 (cost8) to get 1 total = 1+8=9. So the min from 9 is min( 8, 10+ f(3) ). f(3): 3%3=0, divisible. At 3, options: subtract all: cost2, or divide: cost10 to get 1 total10. So f(3)=2. Then f(9) = min(8, 10+2=12) =8. So subtract r then subtract all yields total 1+8=9, same as direct subtract all. Subtract r then divide yields 1+10+ f(3)=1+10+2=13, worse. So f(10)=9.
Now consider possibility: subtract more than r: say subtract 4 (to get 6, divisible). Cost 4, then divide cost10 to get 2, then from 2 subtract 1 to get 1 cost1 -> total 4+10+1=15. Worse. So indeed not better.
But is there scenario where subtract more than r to a lower multiple could be beneficial? Suppose B is negative? No, B>=1. So likely not. But let's try to construct: A is extremely cheap, B moderate, and k large. Suppose n=100, k=10, A=1, B=10. Standard approach: r=0 because 100%10=0. So we decide: divide (cost10) to get 10, then from 10: options: subtract all (9) or divide (10) to get 1. So min from 10 = min(9,10)=9. So total=19. Alternative: subtract all the way from 100: cost99. So best is 19.
Now if we subtract 10 to get 90 (multiple), then divide cost10 to 9, then subtract 8 cost8 -> total 10+10+8=28, worse. So not better.
But what if B is very expensive and A is cheap? Example: n=1000, k=100, A=1, B=10000. r=0? 1000%100=0. Dividing would be extremely expensive. Subtract all: 999. So best is 999. But could we subtract 100 to get 900? That would cost 100, then divide cost10000 to get 9, then subtract 8 cost8 -> total 10108, worse. So no.
But consider if we could skip division entirely? Already considered.
Thus, the only decision points are when n is divisible: divide or subtract all. When n not divisible: either subtract all, or subtract to make it divisible then consider division at that multiple.
But we must be careful: After subtracting to m (largest multiple), we might not want to divide immediately; we could also subtract further to a lower multiple? That would be subtracting additional multiples of k, but that is equivalent to: subtract r, then subtract kt, then divide. That's the same as subtracting (r + kt) then divide. That yields new number (n - (r + k*t))/k = floor(n/k) - t. The alternative path: subtract r, divide to floor(n/k), then subtract t from that result. Let's compare costs:
Path A: subtract s = r + kt, cost sA, then divide cost B, then continue from (floor(n/k)-t) with minimal cost f(floor(n/k)-t). Total cost = (r + k*t)A + B + f(floor(n/k)-t).
Path B: subtract r, divide cost B to get floor(n/k), then subtract t from that number: cost tA, then continue from floor(n/k)-t with minimal cost f(floor(n/k)-t) (but careful: after dividing and subtracting t, we may have to consider that the state after subtracting t might not be the same as in Path A because order differs? Actually in Path B, we first divide then subtract t, leading to same final number floor(n/k)-t. However, the operations cost: rA + B + t*A + f(floor(n/k)-t). Total = (r + t)A + B + f(floor(n/k)-t).
Compare Path A cost: (r + kt)A + B + f(...). Since k>=2, kt >= 2t, Path A costs extra (k*t - t)A = (k-1)tA more than Path B. So Path B is always cheaper (or equal if k=1, but we exclude). Thus, it is never optimal to subtract extra multiples of k before dividing; it's always better to divide as soon as you reach a multiple (the highest multiple below n), and then subtract later if needed. This is a key insight: because subtract cost per unit is constant, and division reduces the number by factor k, doing subtracts after division reduces the number of subtracts needed by factor k. So indeed we should always aim to divide at the largest possible multiple, i.e., after subtracting the minimal amount to make it divisible.
Thus, the optimal strategy is: While n > 1:
- If n % k == 0: we have two choices: either divide (cost B) and set n = n/k, or we could decide to stop dividing and just subtract to 1. But since we are iterating, we can compute at each step the decision: compare the cost of dividing vs subtracting all the way from current n. However, note that if we decide to divide now, we may later divide again. But the decision at each step can be greedy? Let's analyze.
Given the above property, the optimal path from n can be described recursively:
f(n) = 0 for n=1.
For n > 1: If n % k != 0: Let r = n % k. f(n) = min( (n-1)A, rA + f(n - r) )? But f(n - r) we need to evaluate. Since n - r is divisible, we can compute f(n - r) as min( (n-r-1)*A, B + f((n-r)/k) ). So it's like:
Let m = n - r. f(n) = min( (n-1)A, rA + min( (m-1)*A, B + f(m/k) ) )
But note that (n-1)A = rA + (m-1)A. So it's essentially comparing between rA + (m-1)A and rA + B + f(m/k). So it's equivalent to: f(n) = r*A + min( (m-1)*A, B + f(m/k) ). Actually careful: The min between (n-1)A and rA + B + f(m/k) yields:
(n-1)A = rA + (m-1)A. So f(n) = rA + min( (m-1)*A, B + f(m/k) ).
But is it possible that the optimal is not to subtract all the way to m but to subtract to some lower multiple? We already argued it's suboptimal. So this recurrence seems valid.
Now for n divisible (r=0, m=n): f(n) = min( (n-1)*A, B + f(n/k) ). Since r=0.
Thus overall, for n>1: r = n % k. m = n - r. f(n) = r*A + min( (m-1)A, B + f(m/k) )? Actually if r>0, that's the expression. But if r=0, then m=n, and rA=0, so f(n) = min( (n-1)*A, B + f(n/k) ). This fits.
So we have recurrence: f(1)=0. For n>1: let r = n%k, m = n - r (so m is multiple of k). Then f(n) = r*A + min( (m-1)*A, B + f(m/k) ). Note that if r=0, m=n.
But is it always valid to combine like that? Let's verify with examples.
Example 1: n=9,k=2,A=3,B=1. n%2=1 => r=1,m=8. Compute: (m-1)A =73=21. f(m/k) = f(4). Need f(4): 4%2=0 => f(4)=min((4-1)*3=9, B + f(2)=1+ f(2)). f(2): 2%2=0 => f(2)=min((2-1)3=3, 1+f(1)=1+0=1) =1. So f(4)=min(9, 1+1=2)=2. So min((m-1)A=21, B + f(m/k)=1+2=3) => min =3. Then f(9)=rA + that = 13 + 3 =6. Matches.
Example 2: n=5,k=5,A=2,B=20. n%5=0 => r=0, m=5. f(5)=min((5-1)*2=8, 20+f(1)=20) =8. Output 8. Matches.
Example 3: n=19,k=3,A=4,B=2. Compute: n%3=1 => r=1,m=18. (m-1)A=174=68. f(m/k)=f(6). Compute f(6): 6%3=0 => f(6)=min((6-1)*4=20, 2+f(2)). f(2): 2%3? Actually 2<3? But our recurrence applies for any n; we need to define base for n < k? Let's compute: For n=2, k=3, n%3=2? But wait, n < k, then division not possible because we cannot divide by k if n not divisible? Actually division can only be performed if x is divisible by k. If n<k, it might still be divisible? For k=3, n=2 is not divisible, so only subtraction is possible. But our recurrence: for n>1, we compute r=n%k. That yields r=2, m=n-r=0? That would be m=0 which is not >0. That's invalid. So our recurrence as written assumes we can subtract to a multiple of k, but if n<k, the largest multiple less than n is 0? Actually if n<k, then the only multiple of k less than or equal to n is 0 (since 0 is multiple). But subtracting to 0 is not allowed because we need to go to 1, not 0. Actually we could subtract to 1 directly. So our recurrence fails for n<k. Because when n<k, the concept of "subtract to the next lower multiple" doesn't make sense because the next lower multiple is 0, which is less than 1, and we wouldn't want to go there. So we need to treat n<k separately: just subtract to 1, cost (n-1)*A. So for n<k, f(n) = (n-1)*A.
Also, if n is divisible by k, we can divide only if n/k >=1. That's fine if n>=k. For n=k, dividing yields 1. So recurrence works if n>=k. So we need to handle the base: if n==1:0; else if n<k: (n-1)*A. Else (n>=k): proceed with recurrence.
But also careful: When n%k != 0 and n>=k, m = n - r is at least k? Since n>=k and r<n? Actually if n>=k, then the largest multiple of k less than n is at least k if n>=k? Not necessarily: if n=k, r=0, so that's divisible. If n=k+1, r=1, m=k, which is >=k. So m>=k. So then m/k >=1. So recursion works.
But in example 3, we have n=19,k=3, A=4,B=2. n>=k, so compute r=1,m=18. f(6) we need: 6>=3, divisible, f(6)=min((6-1)*4=20, 2+f(2)). Now f(2): 2<k? k=3, so f(2)= (2-1)*4=4. So f(6)=min(20,2+4=6)=6. So min( (m-1)A=68, B+f(6)=2+6=8 ) =8. Then f(19)=14+8=12. Matches output.
Thus recurrence works.
Now we need to compute f(n) efficiently. Since n can be up to 2e9, recursion depth is O(log_k n) if we only follow divisions? But careful: In recurrence, we have min which may involve subtracting all the way, which ends recursion. However, if we follow the recursion for f(n) using this formula, we will compute f for values like n, then possibly m/k, etc. But note that m/k = floor(n/k). So the recursion goes to floor(n/k) when we choose the division path. Also, for n not divisible, we still go to m/k after subtract and division? Actually in the expression f(n) = r*A + min( (m-1)*A, B + f(m/k) ). So to compute f(n), we need f(m/k). m/k = floor(n/k). So recursion goes to floor(n/k). And when we compute f(floor(n/k)), we may again need its floor division, etc. So depth is O(log_k n). That's fine.
But we also have the case where we may need to compute f for numbers that are not exactly floor(n/k) but maybe others? No, only those. So we can implement a recursive function that processes n, with base cases: n==1:0; n<k: (n-1)*A; else: r=n%k, m=n-r, next = m/k; compute f(next) recursively; then compute option1 = (m-1)*A (which is essentially (n-r-1)A) and option2 = B + f(next); choose minOption; then answer = rA + minOption.
We must be careful about overflow: all values up to 2e9, but intermediate calculations like (m-1)*A could be up to (2e9-1)*2e9 = 4e18, which exceeds 32-bit but fits in 64-bit (since 4e18 < 9.22e18). So use 64-bit (long long). The answer might also be up to maybe (n-1)*A ≤ 4e18, so need 64-bit.
But is the recurrence always correct? Let's test with some edge cases.
Case: k=2, n=2, A=5, B=100. n<k? n=2, k=2 so n>=k. Actually n>=k, but n%2=0, so r=0, m=2. f(2)=min((2-1)*5=5, 100+f(1)=100) =5. That's correct: just subtract 1.
Case: n=2, k=3, A=5, B=10. n<k, so f(2)= (2-1)*5=5. That's correct.
Case: k=1: Need special handling because division does nothing and our recurrence would involve division by 1 but m/k = m, leading to infinite recursion. So we handle k=1 separately: answer = (n-1)*A. Because dividing by 1 doesn't change x, and costs B, so it's never beneficial; we can just subtract all the way. But also could we use division to no effect? That would waste coins, so not optimal. So answer = (n-1)*A.
Now, is there any scenario where it's optimal to perform multiple subtracts after some divisions but before the next division? Yes, that's captured because when we compute f(floor(n/k)), we will again apply the same logic; at that number we may decide to subtract to reach next multiple (if not divisible) etc.
Thus the algorithm seems correct.
But let's double-check with more examples, perhaps tricky ones.
Consider n=10, k=3, A=2, B=3. Compute using recurrence: n>=k, r=1, m=9, next=3. f(3): 3%3=0 => f(3)=min((3-1)*2=4, 3+f(1)=3) =3. So minOption = min((9-1)2=16, 3+3=6) =6. So f(10)=12+6=8. Let's try to find a sequence: Option: subtract 1 (2) ->9. Then divide (3) ->3. Then divide (3) ->1. Total 2+3+3=8. Another: subtract 1 (2)->9, subtract all the way from 9: 8 subtracts (16) total 18. Or subtract 7 directly from 10 to 3? 10-7=3 (cost 14), then divide (3) ->1 total 17. So indeed 8 is min.
Now consider scenario where it might be better to not divide even when divisible, but our recurrence accounts for that because min includes (m-1)*A (subtract all from m) vs B+f(m/k). So at m (divisible), we pick the cheaper.
Now consider scenario where n is divisible, but maybe it's cheaper to subtract some to a lower multiple then divide? As argued, that is worse than dividing now then subtracting later. Let's test numeric example: n=27, k=3, A=1, B=10. n divisible. Our recurrence: f(27) = min((27-1)*1=26, 10 + f(9)). f(9): 9%3=0 => f(9)=min((9-1)=8, 10+f(3)). f(3): min((3-1)=2, 10+f(1)=10) =2. So f(9)=min(8,10+2=12)=8. So f(27)=min(26,10+8=18)=18. So optimal cost 18. Path: divide 27->9 cost10, then subtract all 9->1 cost8? Actually 9->1 subtract 8 cost8 total 18. Alternative: subtract 27->1 cost26. Another: maybe subtract 6 from 27 to 21 (cost6), divide (10) to 7, then subtract 6 to 1? 7->1 cost6 => total 6+10+6=22. Or subtract 12 to 15 (cost12), divide (10) to 5, subtract 4 cost4 => total 26. So indeed 18 best.
Now consider case where B is very small and A is large: n=1000000000, k=2, A=1000, B=1. Recurrence will give low cost by dividing as much as possible. Works.
Now we must ensure that the recursion does not cause repeated calculation of same state? But state is just n decreasing by division, and we only go down to 1. So depth is about log_k n, at most about 60 for k=2 and n=2e9. So we can just use recursion or loop.
But careful: In the recurrence, when n%k !=0, we compute r*A + min( (m-1)A, B + f(m/k) ). This requires computing f(m/k). But what about the possibility of not subtracting exactly r to make m, but maybe subtract less? That would not make it divisible, so we cannot divide then. But could we do: subtract some d < r, then later subtract more to become divisible? That's effectively subtracting r anyway but with an intermediate division? No, because after subtract d (<r), we cannot divide because not divisible. We could then subtract more later. The total subtracts to become divisible would still be at least r (since we need to reach a multiple). Actually the minimal subtracts to reach any multiple of k is either r (to go down to next lower multiple) or (k - r) to go up to next higher multiple? But we can only subtract, not add. So we can only go down. So to reach a multiple, we must subtract at least r. So the minimal subtracts to enable a division is r. So any path that eventually divides must include at least r subtracts before that division (unless we first divide when it becomes divisible after some subtracts). There is no way to avoid r subtracts before a division from n. So the minimal cost to enable a division from n is rA + B + cost after division. However, after those r subtracts, we are at m. Could we decide not to divide immediately, but subtract further and then divide later? That would be subtracting extra multiples before division, which we argued is suboptimal compared to dividing then subtracting later. So indeed the recurrence is optimal.
Thus the algorithm is:
if k == 1: print((n-1)*A) else: ans = 0? Actually we can compute recursively or iteratively.
We can implement a function long long solve(long long n) that returns min cost.
Pseudo:
function cost(n): if n == 1: return 0 if n < k: return (n-1)*A r = n % k if r == 0: // divisible return min( (n-1)*A, B + cost(n/k) ) else: // not divisible // m = n - r // next = m / k // option1 = (m-1)A // subtract all from m to 1 // option2 = B + cost(next) // minOption = min(option1, option2) // return rA + minOption
But careful: In the case r != 0, the option1 corresponds to subtracting all the way from m to 1, but we have already subtracted r to reach m. So total would be r*A + (m-1)*A = (n-1)*A, which is the cost of subtracting all the way from n. So indeed option1 essentially yields subtract all the way from n, same as before. But we are taking minOption between (m-1)A and B + cost(next). So rA + (m-1)A = (n-1)A; rA + (B + cost(next)) = rA + B + cost(next). So f(n) = min( (n-1)A, rA + B + cost(next) ). But is it possible that (n-1)A is less than rA + (m-1)*A? Actually they are equal. So minOption essentially chooses between (m-1)A and B+cost(next). Then f(n) = rA + min( (m-1)*A, B + cost(next) ). This is exactly what we have.
But we must be careful: In the case r != 0, we have also the possibility of not even going to m? Could we stop earlier? That would be subtract all the way from n directly, which is covered by the term (n-1)A = rA + (m-1)*A. So it's covered by taking minOption = (m-1)*A? Yes, because if we set minOption = (m-1)A, then total = rA + (m-1)*A = (n-1)*A. So that's fine.
Now we need to handle potential overflow in multiplication. Use unsigned long long? We'll use long long (signed 64-bit). Since max n is 2e9, A up to 2e9, product (n-1)*A up to 4e18, which is within 9.22e18 (max of signed 64-bit). So safe.
Now we must implement recursion with depth up to 60, fine.
But is there any nuance for when k > n? Already handled by base case n<k: cost = (n-1)*A. This includes the case where n is 1? Actually if n=1, we return 0. Base case n<k includes n=1? But if n=1, then n<k (if k>1) but we should return 0 not (1-1)*A=0 anyway. So it's same. But to be safe, check n==1 first.
Now we must also handle k=0? Not allowed, k>=1.
Now, does this recurrence always produce the minimum? Let's attempt to prove more formally.
We can think of the optimal path as a sequence of operations. Consider the last division (if any). Let the number just before the last division be d (which is divisible by k). After division we get d/k, and then we may perform some subtracts to reach 1. So the cost from d onward is either: if we don't divide at d, we just subtract to 1. So for d, optimal is min((d-1)A, B + f(d/k)). For any number x that is not divisible, before we can divide, we must subtract at least x%k to reach a multiple. After subtracting that, we are at m = x - (x%k). At that point, the optimal cost from m is as above. Since subtracts are irreversible, any optimal path from x either never divides (so subtract all) or at some point divides, and the first division must occur at some multiple m' which is ≤ x and is reachable by subtracting some amount s where s ≡ x mod k, and s is the smallest such? Actually the first division could happen at any multiple m' = x - s, where s ≡ x mod k, s>= x%k. But we argued that doing extra subtracts before the first division is suboptimal because you could instead divide earlier and then subtract later, reducing total subtracts. Formal proof: Suppose we choose to subtract s = r + tk (t>=1) then divide, getting to (x - s)/k = floor(x/k) - t. Cost = sA + B + f(floor(x/k) - t). Alternative: subtract r, divide, then subtract t from the result: cost = rA + B + tA + f(floor(x/k) - t) = (r + t)A + B + f(...). Since s = r + tk, difference is (tk - t)A = t(k-1)*A, which is positive for k>1, t>=1. So the alternative is cheaper. So the optimal first division occurs at the largest multiple, i.e., after subtracting exactly r. So indeed we can restrict to that.
Thus recurrence stands.
Now we need to code. But we can also implement iterative method: start ans=0, and while n>1, but careful because decisions may change based on future? Actually we can simulate greedy? Not exactly, because at each step we need to decide whether to divide or subtract all based on future costs. But we can compute f recursively.
But we could also compute using DP bottom-up? Since we only need values for n, floor(n/k), floor(floor(n/k)/k), etc., we can compute recursively.
Implementation:
#include <iostream> using namespace std; long long n, k, A, B; long long solve(long long x) { if (x == 1) return 0; if (k == 1) return (x-1)*A; // Actually handled earlier, but we can have it here too, but careful infinite recursion. if (x < k) return (x-1)*A; long long r = x % k; if (r == 0) { long long next = x / k; long long cost_div = B + solve(next); long long cost_sub_all = (x-1)*A; return min(cost_sub_all, cost_div); } else { long long m = x - r; long long next = m / k; // option1: from m, subtract all to 1 -> cost (m-1)*A; total = r*A + (m-1)*A = (x-1)*A // option2: from m, divide then continue -> cost B + solve(next) long long cost_option2 = B + solve(next); long long cost_option1 = (m-1)*A; // we will add r*A later // Actually we can compute minOption = min(cost_option1, cost_option2) // Then total = r*A + minOption return r*A + min(cost_option1, cost_option2); } } int main() { cin >> n >> k >> A >> B; if (k == 1) { cout << (n-1)*A << endl; } else { cout << solve(n) << endl; } return 0; }But we need to use long long for all. In C++ int might be 32-bit, so use long long.
But wait, in the case r != 0, cost_option1 = (m-1)*A. However, (m-1)*A might overflow if m is large and A large? But m up to n (2e9), A up to 2e9, product up to 4e18, fits in 64-bit signed. Good.
Now we should test with given examples.
Let's manually compute.
Example 1: n=9,k=2,A=3,B=1 -> solve(9) as earlier returns 6.
Example 2: n=5,k=5,A=2,B=20 -> solve(5): x%5==0 -> cost_div = 20 + solve(1)=20, cost_sub_all = (5-1)*2=8 -> min=8 -> output 8.
Example 3: n=19,k=3,A=4,B=2 -> solve(19): r=1,m=18,next=6, cost_option1=(18-1)*4=68, cost_option2=2+solve(6). solve(6): x%3==0, cost_div=2+solve(2), cost_sub_all=(6-1)*4=20. solve(2): x<k? 2<3 -> (2-1)4=4. So cost_div=2+4=6, cost_sub_all=20 -> min=6. So cost_option2=2+6=8. minOption = min(68,8)=8. total = 14 + 8 =12. Output 12.
All good.
Now consider edge: n=2e9, k=2, A=1, B=1. Should be cheap.
But we must also consider possibility that B is so cheap that it's always better to divide. But the recurrence will handle.
Now, is there any scenario where the recursion leads to repeated calls to the same n? Since each call reduces n to floor(n/k) or to base, it's a strictly decreasing sequence (except if n is same? For k=1 we handled separately; for k>1, floor(n/k) < n for n>=2). So no cycles.
Now, we must also consider that in the case r != 0, we compute solve(next). But what if next is 0? That would happen if m/k = 0, i.e., m < k. But m = n - r, with n >= k and r < k. So m >= n - (k-1). Could m be less than k? If n = k, then r = 0, so that case is separate. If n = k+1, r=1, m = k, which is >= k. So m/k = 1, not 0. If n = k, r=0 handled. If n is between k and 2k-1, then m = k (since n - r = largest multiple less than n, which is k). So m/k = 1. So next is at least 1. So no zero.
Thus safe.
Now, complexity: O(log_k n) recursion depth. That's fine.
But is there any nuance about when (n-1)*A might overflow if we compute? Use long long.
Now, double-check correctness with some random tests via brute force for small n, k, A, B to verify. We'll do mental check.
Let's test n=7,k=3,A=2,B=3.
Our recurrence: n>=k, r=1,m=6,next=2. f(2): 2<3 -> (2-1)*2=2. cost_option1=(6-1)2=10, cost_option2= B + f(2)=3+2=5 -> minOption=5. total = rA + 5 = 2+5=7. So f(7)=7.
Now brute force: possible sequences:
- Subtract all: 6 subtracts cost 12.
- Subtract 1 (2) ->6, then divide (3)->2, then subtract 1 (2)->1: total 2+3+2=7.
- Subtract 4 (8) ->3? Actually 7-4=3 (cost8), then divide (3) ->1 total 11.
- Subtract 4 to 3 but 3 divisible, could also divide: 7->3 (subtract4 cost8), divide (3) cost3 ->1 total 11.
- Subtract 1 to 6, then subtract all from 6: 5 subtracts (10) total 12. So min=7. Good.
Now test n=10,k=3,A=2,B=7. (B higher). Recurrence: r=1,m=9,next=3. f(3): n%3=0 => cost_div=7+f(1)=7, cost_sub_all=(3-1)*2=4 => f(3)=4. cost_option1=(9-1)*2=16, cost_option2=7+4=11 -> minOption=11. total=2+11=13. So f(10)=13. Brute force:
- Subtract all: 9*2=18.
- Subtract1 (2)->9, then divide (7)->3, then subtract2 (4)->1 total 2+7+4=13.
- Subtract1->9, then subtract all from9:8*2=16 total 18.
- Subtract4 to6? 10-4=6 (cost8), then divide (7)->2, then subtract1 (2)->1 total 8+7+2=17.
- Subtract7 to3 (cost14), divide (7) ->1 total21. So min=13.
Now test case where dividing at a later stage might be better than dividing immediately? For instance, n=8,k=2,A=10,B=10. Our recurrence: n%2=0 => f(8)=min((8-1)*10=70, 10+f(4)). f(4): min((4-1)*10=30, 10+f(2)). f(2): min((2-1)*10=10,10+f(1)=10)=10. So f(4)=min(30,10+10=20)=20. f(8)=min(70,10+20=30)=30. So optimal cost 30. Path: divide 8->4 (10), divide 4->2 (10), subtract 1 (10) ->1? Actually from 2 to 1 subtract cost10, total 30. Alternative: subtract all from 8: 70. Could there be a path: subtract 2 to get 6? 8-2=6 (20), then divide 6->3? But 6 divisible by 2, divide cost10 ->3, then subtract 2 to 1? 3-2=2? Actually to get to 1 from 3: subtract 2 cost20? That would be 20+10+20=50. Not better. What about subtract 1 to 7 (10), then? 7 not divisible by2, need to subtract 1 to 6 (10) then divide (10) to 3, then subtract 2 (20) total 50. So optimal is indeed divide twice and subtract once. But could we skip a division and do more subtracts? Already considered. So recurrence works.
Now test with k large relative to n: n=5,k=10,A=5,B=1. n<k -> f(5)= (5-1)*5=20. Is there any possible division? No, because n not divisible? Actually we can't divide because n not divisible, and to become divisible we'd have to subtract down to 0? Not allowed. So 20 is correct.
Now test where division might be possible but expensive, and subtract all is cheaper: n=100,k=10,A=1,B=1000. f(100): divisible, cost_div=1000+f(10). f(10): divisible, cost_div=1000+f(1)=1000, cost_sub_all=9 => f(10)=9. So cost_div=1009, cost_sub_all=99 => min=99. So f(100)=99. Good.
Now test where r != 0 and B is moderate: n=11,k=2,A=5,B=6. n%2=1,r=1,m=10,next=5. f(5): 5>=2, 5%2=1,r=1,m=4,next=2. f(2): 2%2=0, f(2)=min((2-1)5=5, 6+f(1)=6) =5. For f(5): cost_option1=(4-1)5=15, cost_option2=6+f(2)=6+5=11, minOption=11. total f(5)=rA+min=15+11=16. Now for n=11: cost_option1=(10-1)5=45, cost_option2=6+f(5)=6+16=22, minOption=22, total=15+22=27. So f(11)=27. Let's check manually: Option: subtract1 (5) ->10, divide (6) ->5, then from 5 to 1? From 5 optimal? 5 to 1: subtract1 to4 (5), then divide 4->2 (6) then subtract1 (5) = total 5+6+5+6+5? Actually we computed f(5)=16, so from 5 the optimal cost is 16. So total from 11: 5+6+16=27. Alternative: subtract all from 11: 105=50. Or subtract1->10, then subtract all from10:9*5=45 total 50. Or subtract3 to 8? 11-3=8 cost15, divide 6->4, then from 4: divide 6->2, subtract1 5 -> total 15+6+6+5=32. So 27 seems optimal.
Now test with B very small and A large: n=1000,k=2,A=1000,B=1. f(1000) will be cheap because we divide a lot. We can compute quickly: recursion: many divisions, cost = about log2(1000)1 + some subtracts? Let's approximate: typical binary reduction: each division reduces number significantly; subtracts only needed for remainders. Since A large, we want to minimize subtracts, but we might need to subtract to make numbers even. For 1000 (even), no subtract, divide ->500 (cost1). 500 even -> divide ->250 (1). 250 even ->125 (1). 125 odd: r=1, subtract1 (1000) to 124? Wait 125-1=124 (cost A=1000), then divide ->62 (1). Then 62 even ->31 (1). 31 odd: subtract1 (1000) to30, divide->15 (1). 15 odd: subtract1 (1000) to14, divide->7 (1). 7 odd: subtract1 (1000) to6, divide->3 (1). 3 odd: subtract1 (1000) to2, divide->1 (1). Total subtracts: 125->124, 31->30, 15->14, 7->6, 3->2: 5 subtracts, each cost 1000 -> 5000; plus divisions: about 10 divisions? Actually count: 1000->500 (1),500->250 (1),250->125 (1),125->62 (after subtract1 then divide) we count subtract1 and divide; then 62->31 (1),31->15 (subtract1+divide),15->7 (subtract1+divide),7->3 (subtract1+divide),3->1 (subtract1+divide). Divisions: from 1000,500,250,125? Actually 125 after subtract becomes 124 then divide, so division from 124->62, that's one; 62->31 division; 31 after subtract becomes 30 divide to 15; 15 after subtract becomes 14 divide to 7; 7 after subtract becomes 6 divide to 3; 3 after subtract becomes 2 divide to 1. So divisions: 1000,500,250,124? Actually 125 we subtracted, so division count: starting from 1000: we divide at 1000,500,250? Wait sequence: x=1000 (even): divide: 1000/2=500 (div1) 500 divide: 250 (div2) 250 divide: 125 (div3) Now 125 odd: subtract1 ->124, then divide: 124/2=62 (div4) 62 divide ->31 (div5) 31 odd: subtract1->30, divide->15 (div6) 15 odd: subtract1->14, divide->7 (div7) 7 odd: subtract1->6, divide->3 (div8) 3 odd: subtract1->2, divide->1 (div9) So total divisions = 9, total subtracts = 5, total cost = 91 + 5*1000 = 9 + 5000 = 5009. Our recurrence should compute similarly.
Now if we just subtracted all from 1000: 999*1000 = 999000, much higher. So division is beneficial.
Now, what about scenario where we might want to subtract more than remainder before division if B is negative? Not allowed.
Thus recurrence seems robust.
But we must consider the case when k is not a divisor of n but we might want to subtract to a number that is not a multiple and then maybe subtract further to become multiple later? That's effectively covered because after subtracting r, we are at m; from m we could either divide or not. If we don't divide, we could subtract further. But that would be captured by cost_option1 which is subtract all from m to 1. That path corresponds to: subtract r to get to m, then subtract (m-1) to get to 1: total subtract all from n. So it's the "never divide" path. If we want to divide later (after some more subtracts from m), that would be like: subtract r to m, then subtract some multiples of k (tk) to get to m - tk, then divide. As argued, that is always worse than dividing at m then subtracting t. So we don't need to consider it.
Now, edge case: n is huge, and k is also huge (like 2e9). Then n<k? Possibly n might be less than k. Then f(n) = (n-1)*A. That's straightforward.
Now, let's test with a scenario where k > n but n is divisible? Actually if k > n, the only multiple of k <= n is 0. So division impossible. So f(n) = (n-1)*A. So base case n<k covers that, even if n is divisible? For example, n=10, k=20: n<k, so f(10)=(10-1)*A. That's correct because dividing 10 by 20 not allowed (only if divisible, but also division reduces to 0.5? Not integer, so cannot). So correct.
Now, confirm that our recurrence for n>=k works for k > n? Already excluded because n<k case.
Now, we should also ensure that when k=0? Not possible.
Thus, solution is clear.
But is there any scenario where the recurrence could be simplified to a loop? Possibly we could implement a while loop that accumulates cost while handling remainders. For efficiency, we could simulate from n down to 1 using the greedy concept but with decision at each divisible step. But because the decision at a given state depends on future (via f(next)), we can't just greedily decide. However, we can compute f recursively which essentially does the same.
However, we could also compute iteratively by considering that the optimal strategy is to either never divide or to perform divisions at certain points. Since division is beneficial only if the cost of division plus the cost of subtracting remainders is less than the cost of subtracting the difference between numbers. But we already encoded the comparison in the recurrence.
One might attempt to compute from bottom up: start from 1 and multiply, but not needed.
Now, we should check for potential pitfalls: integer overflow in multiplication (n-1)*A might exceed 64-bit? n max 2e9, A max 2e9 -> product 4e18, which fits in signed 64-bit (max 9.22e18). So safe.
But what about intermediate in recursion: r*A where r up to k-1, but k up to 2e9, so r up to ~2e9, A up to 2e9, product up to 4e18, still safe.
So we are good.
Now, but wait: In the case r != 0, we compute (m-1)*A, where m can be as large as n, up to 2e9. So product up to 4e18.
Now, consider recursion depth: For k=2, n=2e9, depth about 31. For k=2, n=2e9 ~ 2^31, so about 31 levels. For k=3, depth about log_3(2e9) ~ 19. So fine.
Now, we need to ensure that we don't hit recursion limit in some languages (like Python default recursion limit 1000, but depth is small; in C++ recursion depth of 60 is fine).
Thus solution is good.
But I recall that some solutions for this problem (from Codeforces) use a loop: while n > 1, if n%k == 0, compare (n - n/k)*A with B? Actually there is known problem "A and B and ..." but I'm not completely sure. Let's see if we can derive a non-recursive approach: At each step, we could decide to divide if B <= (n - n/k)*A? That's a local greedy condition: dividing is beneficial if the cost of division is less than the cost of subtracting to reach the same point (i.e., from n to n/k, you could either divide (cost B) or subtract (n - n/k) times (cost (n - n/k)*A). But it's not that simple because after division you might have further reductions, and subtracting directly to n/k might not be the optimal alternative if you plan to divide later. However, the recurrence we derived essentially reduces to a greedy: At each divisible n, we compare (n - n/k)*A (the cost to reduce from n to n/k by subtracting) with B, and if B is less, we should divide? But the recurrence for divisible n is min( (n-1)*A, B + f(n/k) ). This is not simply comparing (n - n/k)*A to B, because (n-1)*A is the cost to subtract all the way. But maybe we can transform: f(n) = min( (n-1)*A, B + f(n/k) ). Suppose we assume that it's optimal to use division at some points. Could it be that the optimal decision at each divisible n is to divide if B < (n - n/k)*A? Not exactly. Consider example: n=4, k=2, A=5, B=6. (n - n/k)*A = (4-2)*5=10. B=6 which is less than 10. So if we used local condition B < (n - n/k)*A we would divide. But is it optimal? Let's compute f(4): (4-1)*5=15, B + f(2)=6+ f(2). f(2): (2-1)*5=5, B + f(1)=6 => f(2)=5. So B+f(2)=11. So f(4)=min(15,11)=11. So dividing gives 11, subtract all gives 15. But what if we subtract from 4 to 2? That would cost (4-2)*5=10, then from 2 subtract to 1 cost5 => total 15. So dividing is indeed better (11 vs 15). So dividing is better. Now consider n=4,k=2,A=5,B=10. (n-n/k)*A=10, B=10 equal. Local condition might say not beneficial (or indifferent). Compute f(4): (4-1)*5=15, B+f(2)=10+5=15 => tie. So both 15. So condition B <= (n-n/k)*A gives same result? But consider n=4,k=2,A=1,B=10. (n-n/k)*A=2, B=10 >2. So local would say don't divide. f(4): (4-1)*1=3, B+f(2)=10+1=11 => min=3, so subtract all. So condition works? Maybe the recurrence reduces to: for divisible n, we should divide only if B + f(n/k) <= (n-1)*A. But f(n/k) might be less than (n/k-1)*A if further divisions are beneficial. So it's not a simple local comparison. However, we can substitute the recurrence for f(n/k). In many cases, if division is beneficial at larger numbers, it will also be beneficial at smaller numbers? Not always; maybe at some level division becomes not beneficial. So we need recursion.
But perhaps we can compute iteratively from the bottom? Since recursion depth is small, it's fine.
Now, verify with an example where local condition might fail: Suppose n=27,k=3,A=1,B=15. Compute (n - n/k)*A = (27-9)*1=18, B=15 <18, so local says divide. But maybe it's better not to divide at 27 because after dividing, we might have to do more expensive divisions later? Let's compute f(27): f(9) we need. f(9): (9-1)*1=8, B + f(3)=15 + f(3). f(3): (3-1)*1=2, B+f(1)=15 => f(3)=2. So B+f(3)=17, so f(9)= min(8,17)=8. So f(27)= min((27-1)=26, 15+8=23) => 23. So dividing yields 23, subtract all yields 26. So dividing is better. So local works.
Consider n=27,k=3,A=5,B=2. (n - n/k)*A = (27-9)*5=90, B=2 <<90, so divide. f(27): f(9): (9-1)*5=40, B+f(3)=2+f(3). f(3): (3-1)5=10, B+f(1)=2 => f(3)=2 (since 2<10). So f(9)= min(40,2+2=4)=4. f(27)= min(130, 2+4=6)=6? Wait (27-1)5=265=130, B+f(9)=2+4=6 => f(27)=6. That seems incredibly low! Check: n=27, k=3, A=5, B=2. Can we achieve cost 6? Strategy: divide 27 -> 9 (cost2), divide 9->3 (cost2), divide 3->1 (cost2). That's 6. But note: 27 divisible by 3, 9 divisible by 3, 3 divisible by 3. So yes, we can do three divisions, cost 2 each = 6. Subtract all would be 265=130. So dividing is far better. Local condition also says divide. So no problem.
Now consider scenario where local condition suggests dividing at high n but later divisions might be too expensive, causing overall cost maybe higher than subtracting all? But if later divisions are expensive, maybe we would not divide later. But we might still benefit from the first division. But could it be that dividing at high n leads to a state where the optimal is to subtract all, and the total B + (m-1)*A is greater than (n-1)*A? That is exactly the comparison in recurrence: B + f(m/k) vs (n-1)*A. If f(m/k) = (m/k - 1)*A (i.e., subtract all from that state), then we compare B + (m/k - 1)*A vs (n-1)*A. Since m = n when divisible, we compare B + (n/k - 1)*A vs (n-1)*A. This is equivalent to comparing B vs (n - n/k)*A. Because (n-1)*A - (n/k - 1)*A = (n - n/k)*A. So if f(m/k) = (m/k -1)*A, then divide is better iff B < (n - n/k)*A. So the local condition matches when the optimal from n/k is to subtract all. If f(n/k) is less than (n/k-1)*A (because further divisions are beneficial), then B + f(n/k) is even smaller, so divide is even more beneficial. So the decision to divide at n is at least as good as the local condition suggests. Therefore, we can actually use a greedy: at each step when n is divisible by k, if B <= (n - n/k)*A, then divide (because even if we later just subtract all from n/k, it's not worse than subtracting from n; but if B > (n - n/k)*A, it might still be beneficial to divide if later we can do further divisions that reduce cost? Let's test: Suppose B is slightly larger than (n - n/k)*A, but if dividing now allows us to do a subsequent division that saves a huge amount, overall might be cheaper. Example: n=100, k=10, A=1, B=12. (n - n/k)*A = (100-10)*1=90. B=12 <90, so divide anyway, so not interesting. Need B > (n - n/k)*A. Try to construct: n=1000, k=10, A=10, B=2000. (1000-100)*10 = 9000, B=2000 <9000, still less. So B is smaller. To have B > (n - n/k)*A, B must be large relative to A and n. Suppose A is tiny, B large: n=1000, k=10, A=1, B=2000. (n - n/k)*A = 900, B=2000 >900. So local condition says don't divide. But maybe dividing now could lead to subsequent divisions that save a lot? Let's compute f(1000) with A=1,B=2000. n=1000 divisible, so f(1000) = min((1000-1)*1=999, 2000 + f(100)). f(100): (100-1)=99, 2000+f(10). f(10): (10-1)=9, 2000+f(1)=2000 => f(10)=9 (since 9<2000). So f(100)= min(99, 2000+9=2009) =99. So f(1000)= min(999, 2000+99=2099) =999. So indeed subtracting all is optimal. So local condition holds.
What about a scenario where B is greater than (n - n/k)*A but dividing now enables a future division that is extremely cheap? But B is fixed; dividing at any step costs B. If B is large, each division is expensive. For dividing to be worthwhile, the total cost saved by divisions must outweigh the total B paid. Since subtract cost per step is constant A, dividing by k reduces the number by factor k, which saves about (k-1)/k of the remaining subtracts? Actually, consider from a number m divisible: if you divide, you go to m/k; if you don't divide, you could subtract (m - m/k) to reach m/k. So the immediate saving from dividing rather than subtracting to that same point is (m - m/k)*A - B. If that's negative, dividing at that step alone is not beneficial. However, dividing may allow further divisions. But if you divide, you'll have to pay B again for each division. So if at each potential division step the immediate saving is negative, then doing any division would likely increase total cost. But could there be a case where immediate saving is negative at a high level but positive at a lower level, and the combination yields net positive? Example: At high n, (n - n/k)*A is huge, so B might be less; but we are examining B > (n - n/k)*A, which means immediate saving is negative. At lower n, (n' - n'/k)*A is smaller, so B might be even larger relative? Actually as n decreases, (n' - n'/k)*A decreases. So if B > (n - n/k)*A at high n, then B will certainly be > (n' - n'/k)*A for any n' < n (since (n' - n'/k) < (n - n/k)). So immediate saving is negative at every subsequent division step as well. Therefore, doing any division would be worse than just subtracting at each step. So indeed if B > (n - n/k)*A for the current n, then it's never beneficial to divide at n or any smaller number? Not necessarily: what if k is large and n is just slightly above k? For n=k+something, (n - n/k) maybe small. But if B is larger than that, then division at that n is not beneficial. For smaller n, n/k is even smaller, so (n - n/k) is even smaller, so B is even larger relative, so still not beneficial. So division is never beneficial. Therefore, the decision can be based on comparing B with (n - n/k)*A? But careful: When n is not divisible, we might subtract some to make it divisible. The comparison might involve that remainder cost. But the recurrence already handles it.
Given the recurrence, we can compute directly.
But there is another nuance: In some solutions, they use a loop that while n >= k, they compute remainder, subtract remainder, then if it's worth to divide, they do, else break and subtract the rest. However, they need to decide "worth" based on comparing B with (n - n/k)*A? But as argued, if B is less than (n - n/k)*A, dividing is beneficial (even if later we might not divide). Actually, if B < (n - n/k)*A, then even if after division we just subtract all from n/k, the total cost would be B + (n/k - 1)*A, while subtracting all from n is (n-1)*A. Since (n-1)*A - ((n/k -1)*A) = (n - n/k)*A, the saving is (n - n/k)*A - B. If B < (n - n/k)*A, then B + (n/k-1)*A < (n-1)*A, so dividing now and then subtracting all from n/k is cheaper than subtracting all from n. So it's definitely beneficial to divide at least once. Moreover, after dividing, maybe further divisions are even more beneficial. So we can safely divide when B < (n - n/k)*A. But if B == (n - n/k)*A, then dividing and subtracting all yields same cost as subtracting all, so either is fine. If B > (n - n/k)*A, dividing now and then subtracting all is more expensive than subtracting all from n. However, could dividing now and then doing further divisions (not just subtracting all) yield a lower total? Suppose after division, we might do another division that saves even more. But if B > (n - n/k)*A, then the immediate saving is negative; we incur extra cost now. To still be beneficial overall, the future savings from subsequent divisions must outweigh this extra cost. However, future savings are also of the form (m - m/k)*A - B for some m. If B > (n - n/k)*A, then B is larger than the maximum possible saving from any division? Actually, as n decreases, (m - m/k) decreases, so the potential saving (m - m/k)*A - B becomes even more negative. So it's impossible for future divisions to recoup the loss because each division would also lose money. So overall, if B > (n - n/k)*A for the current n (the largest n we consider), then division is never beneficial at any stage. So we could break and subtract all. This suggests a greedy algorithm:
If k == 1: answer = (n-1)*A. Else: ans = 0 while n > 1: if n % k == 0: // Determine if division is worth if B < (n - n/k)*A: // division is beneficial ans += B n /= k else: // not beneficial, subtract the rest ans += (n-1)*A n = 1 else: // make it divisible by subtracting remainder r = n % k // But we might consider: if after subtracting r, we may decide not to divide. // We need to decide whether to subtract only r or maybe subtract all. // We can compute the cost of dividing after subtracting r, and compare to subtracting all. // This is similar to the recurrence decision. // But maybe we can decide: if after subtracting r, division is beneficial? Actually we need to compare. // Let m = n - r. // The cost to go from n to 1 via subtract all is (n-1)A. // The cost via subtract r then divide then optimal from m/k is rA + B + f(m/k). // Without recursion, we can't know f(m/k) simply. But we could continue loop: after subtracting r, we set n = m and then loop will consider division at m. But we need to decide whether to perform the division or not. However, at the point after subtracting r, we have n = m (divisible). Then in the loop we will evaluate if division is beneficial. But we also need to account for the possibility that after subtracting r, we might decide not to divide and instead subtract all from m. That would be same as subtracting all from n, which we could handle by breaking. So the loop could be:
// Actually we can do: while n > 1: // if n % k != 0: // r = n % k // // We have two options: either subtract all remaining (n-1) and finish, or subtract r to make divisible and continue. // // To decide, we need to compare the cost of subtracting all now vs subtracting r and then possibly dividing. // // However, we don't know yet if after subtracting r we will divide. But we can check: after subtracting r, we get m. // // At m, we can evaluate if division is beneficial using the same condition (B < (m - m/k)*A?) But that condition assumes after division we subtract all. But maybe after division we could further divide. So we'd need recursion again. // So a simple greedy based on local comparison may not be sufficient when remainders are involved, because the decision to subtract r to make divisible might lead to a division that is beneficial, but we need to know that. // However, note that the recurrence is simple enough to implement recursively with O(log n) calls. So I'll stick with recursion.Given that recursion is trivial, we can just implement that.
But there is also a potential optimization: we can compute f iteratively using a while loop that accumulates cost and reduces n, but using the recurrence decisions at each step without recursion. Since the recurrence is self-contained, we can compute it iteratively by simulating from n down to 1, but we need to make decisions that depend on future f(next). However, we can compute f(next) first if we go from bottom up? Not straightforward. Recursion is fine.
Thus, final solution: recursion as described.
But we need to be careful about stack overflow in some languages? In C++, recursion depth 60 is safe.
Now, let's verify with some random test by mental or maybe code later.
Potential pitfalls: For large numbers, the product (n-1)*A may exceed 2^63-1? 2^63-1 is about 9.22e18. n max 2e9, A max 2e9 => product 4e18 < 9.22e18. So safe.
Also, note that B can be up to 2e9, adding to f(next) which can be up to 4e18, still within 64-bit.
Thus, implementation is straightforward.
But is there any case where recursion might cause many repeated calls? Each call reduces n to floor(n/k), so it's linear in depth. Good.
Now, I'll produce final answer.
But I'm ChatGPT, so I need to output code? The user expects an explanation? The problem statement: "Right now she actually isn't. But she will be, if you don't solve this problem." It's a programming problem. The output is the answer. But as ChatGPT, I need to produce the solution in text? Probably they want the code? But the user didn't specify; they gave the problem and ask for solution? Usually these are from Codeforces. The user likely expects the solution reasoning and possibly code. But as per instructions, "You are ChatGPT, a large language model ... Provide answer in requested format." The user didn't explicitly request code; they gave input/output examples and asked "What is the minimum amount of coins?" Possibly they want a program to solve it? But since this is a conversation, maybe they want me to compute for given input? No, they gave general problem.
Actually the prompt: "You are given integers n, k, A and B... Output a single integer — the minimum amount of coins..." It's a problem description. They likely expect me to write a solution, maybe in code. But typical interaction: user provides a problem, assistant provides solution explanation and code.
Given the system instructions: "You should not produce any output. You should reason step by step." But that is about something else? Actually the system prompt: "You are ChatGPT... Follow the user's instructions carefully." The user asked: "Right now she actually isn't. But she will be, if you don't solve this problem." That seems like a story. Then they present the problem. They likely want me to output the answer for given inputs? But the problem statement says "Input: ..." and "Output: ..." and they gave examples. They didn't give specific numbers; they gave a problem statement. So they are asking me to solve the problem (i.e., devise an algorithm and perhaps produce code). Usually in these settings, I respond with an explanation and then code (in C++ or Python). Since the user did not specify language, I can provide a solution in C++ (commonly used for such problems) or Python.
I'll assume they want a solution: an algorithm explanation and then code.
But note: The instruction: "You are ChatGPT... Provide answer in requested format." The user didn't explicitly request a format. So I'll provide a clear explanation and then provide the code in C++.
Given that the problem is from Codeforces (I think problem "Masha and Bears"? Actually it's "A and B and Chess"? Not sure). But I recall a Codeforces problem "A and B and Team Training" is different. There is a problem "C. Minimum number of steps" maybe. But anyway.
Let's just produce the final answer.
Before final, let's test additional tricky cases.
Case: k=2, n=3, A=5, B=100. n%2=1, r=1,m=2,next=1. cost_option1=(2-1)5=5, cost_option2=100+0=100, minOption=5. total=15+5=10. So f(3)=10. That's correct: subtract 1 (5) ->2, subtract 1 (5) ->1. Total 10. Not dividing because expensive.
Case: n=3,k=2,A=5,B=1. r=1,m=2,next=1. cost_option1=5, cost_option2=1+0=1, minOption=1, total=5+1=6. So f(3)=6. Path: subtract1 (5) to 2, divide (1) to 1 => total 6. Yes.
Case: n=1,k anything: output 0.
Now check n=2,k=2,A=5,B=100: divisible, cost_div=100+f(1)=100, cost_sub_all=5 => min=5 => subtract.
Now test n=1000000000, k=1000000000, A=1, B=1. n>=k, n%k? 1000000000 % 1000000000 = 0, so f(n)=min((n-1)*1=999999999, 1+f(1)=1) => 1. That's correct: divide once to 1.
But wait: n/k = 1, so one division yields 1, cost 1. So answer 1.
Now test n=1000000000, k=1000000000-1, A=1, B=1. n%k = 1000000000 mod (1e9-1) = 1? Actually 1e9 mod (1e9-1) = 1. So n<k? Actually k is almost n but less? n=1e9, k=999999999, so n>k. r=1, m= n -1 = 999999999, which is equal to k. So m/k = 1. Compute: f(1e9) = r*A + min( (m-1)*A, B + f(1) ) = 1 + min( (999999998)*1, 1+0 ) = 1 + min(999999998,1) = 2. So answer 2. Indeed: subtract 1 (cost1) to 999999999, divide (cost1) to 1. So 2.
Works.
Now, we must also consider scenario where k is huge but n is just above k, remainder r could be as large as k-1 (which could be up to 2e9-1). So r*A could be huge (up to 4e18). That's fine.
Now, we need to make sure that we don't have integer division rounding issues: we use integer arithmetic.
Now, possible improvements: We could write an iterative version that processes n from top to bottom using a while loop and accumulating ans, but still using recursion or maybe a stack. But recursion is simpler.
But some judges might have recursion limit issues if we use recursion in Python? But we are writing C++.
Now, final code in C++:
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n, k, A, B; ll solve(ll x) { if (x == 1) return 0; if (x < k) return (x - 1) * A; ll r = x % k; if (r == 0) { ll next = x / k; ll cost_div = B + solve(next); ll cost_sub_all = (x - 1) * A; return min(cost_sub_all, cost_div); } else { ll m = x - r; // largest multiple of k less than x ll next = m / k; ll cost_option1 = (m - 1) * A; // subtract all from m ll cost_option2 = B + solve(next); return r * A + min(cost_option1, cost_option2); } } int main() { cin >> n >> k >> A >> B; if (k == 1) { cout << (n - 1) * A << endl; return 0; } cout << solve(n) << endl; return 0; }But careful: In the else branch, we used (m - 1) * A. However, we need to ensure that we are not missing the case where after subtracting r, we might decide not to divide and also not subtract all from m? That's the same as subtract all from n. So fine.
Alternatively, we could directly compute:
ll ans = 0; while (n > 1) { if (n % k == 0) { if (B < (n - n/k) * A) { ans += B; n /= k; } else { ans += (n - 1) * A; break; } } else { ll r = n % k; // We need to decide: either subtract all or subtract r and then possibly divide. // But we don't know if dividing after r is beneficial. // Could compute: if B < ( (n - r) - (n - r)/k ) * A? Not exactly. // So recursive is safer. } }But as argued earlier, we could still decide: at this point, we can subtract r, get to m, and then in next iteration we will decide about division. However, the decision to subtract r might be wasteful if we later decide not to divide. But we can incorporate that by comparing the cost of subtracting all from n vs subtracting r and then from m taking the optimal (which we don't know yet). To avoid recursion, we could simulate and keep track of future? Not necessary.
Given that recursion is easy, we'll stick with it.
But we need to ensure that the recursion doesn't cause stack overflow for worst-case depth ~60, it's fine.
Thus, final answer.
But wait: There is also a scenario where n is divisible, but after division we may need to subtract some before next division. Our recurrence will handle that because we compute f(next) recursively.
Now, I'll produce final answer: explanation and code.
But maybe we can also provide Python solution for readability. However, given that the problem originally likely from Codeforces, C++ is typical. But I'll provide both? I'll provide C++.
Now, double-check the special case k=1: Our main handles it, but if we accidentally call solve with k=1, then in solve when x>=k (since k=1, x>=1 always) and we compute r = x%1 = 0, then m=x, next=x/1=x, causing infinite recursion. So we must handle k==1 outside.
Now, also consider k=0? Not allowed.
Thus, final code is good.
Now, I'll include some comments.
But before final, we should test with the sample inputs.
Sample 1:
Input: 9 2 3 1
Our code: k!=1, solve(9): 9%2=1, r=1,m=8,next=4. cost_option1=(8-1)3=21, cost_option2=1+solve(4). solve(4): 4%2=0, next=2, cost_div=1+solve(2), cost_sub_all=33=9. solve(2): 2%2=0, cost_div=1+solve(1)=1, cost_sub_all=13=3, min=1 => f(2)=1. So f(4)=min(9,1+1=2)=2. So cost_option2=1+2=3. minOption=min(21,3)=3. total=13+3=6. Output 6.
Sample2: 5 5 2 20
k!=1, solve(5): 5%5=0, cost_div=20+0=20, cost_sub_all=4*2=8 -> min=8, output 8.
Sample3: 19 3 4 2
Already computed 12. So correct.
Thus, answer.
Now, what about potential performance issue due to recursion? It's fine.
Now, I'll produce final answer with explanation and code.
But the user might just want the answer? Actually the prompt: "You are given integers n, k, A and B... Output a single integer" - looks like they want me to output the answer for specific input? But they didn't provide specific numbers; they provided examples. Hmm.
Wait, the problem statement is generic. There's no actual values given after the description except examples. The user says: "Right now she actually isn't. But she will be, if you don't solve this problem." Then they give the problem. Possibly they want me to write a program that reads input and outputs the answer. That's typical for these "solve this problem" prompts. So I should provide a solution in code.
Given the instructions in the problem: Input: first line n, etc. So indeed it's a coding problem.
Thus, I'll output the code.
But as ChatGPT, I'm supposed to provide the final answer. I'll provide the C++ code.
Now, ensure we use long long and maybe faster I/O.
Potential micro-optimizations: none needed.
Now, we might also consider an iterative DP using a while loop and a variable ans, but using recursion is fine.
One more check: For n divisible, we compute (x-1)*A which could be large. Could there be a risk that (x-1)*A overflows signed 64-bit? As said, max 4e18 < 9.22e18. So safe.
Now, I think it's correct.
I'll now produce final answer with explanation and code. ```cpp #include #include using namespace std;
typedef long long ll;
ll n, k, A, B;
// returns minimum cost to reduce x to 1 ll solve(ll x) { if (x == 1) return 0; if (x < k) return (x - 1) * A; // cannot divide, only subtract
ll r = x % k; if (r == 0) { // x is divisible by k ll next = x / k; ll cost_div = B + solve(next); ll cost_sub_all = (x - 1) * A; return min(cost_sub_all, cost_div); } else { // make x divisible by subtracting the remainder ll m = x - r; // largest multiple of k less than x ll next = m / k; // best cost from m: either subtract all or divide ll best_from_m = min((m - 1) * A, B + solve(next)); return r * A + best_from_m; }}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k >> A >> B; // division by 1 does nothing, so only subtracts are useful if (k == 1) { cout << (n - 1) * A << '\n'; return 0; } cout << solve(n) << '\n'; return 0;}