We start with 0 and we have to reach n

We can perform 3 operations:

Multiply the current number by 2 (cost p)

Multiply the current number by 3 (cost q)

Increase/Decrease the current number by 1 (cost r)

Find the min-cost to reach from 0 to n

```
Constraints:
10 testcases
1 <= n <= 10^18
1 <= p,q,r <= 10^9
```

Example:

n,p,q,r = 11,1,2,8

Answer : 20

Order: +1, *3, *2, *2, -1 = 8 + 2 + 1 + 1 + 8 = 20

Maybe generate all natural x and y such that $$$2^x 3^y \leq n$$$. There exist only $$$O(log^2(n))$$$ such pairs. Get the minimum cost seeing the solution generated by each pair.

UPD: Not always the optimal strategy. By seeing the editorial provided in the comments below, it seems we should start backwards and either decrease until zero or decrease until find a multiple of 2 or 3 of the form $$$k \ floor(\frac{n}{k})$$$ or $$$k \ ceil(\frac{n}{k})$$$. So the solution is always of the form $$$\sum c_i + \sum 2^{a_j} 3^{b_j}$$$.

The first step makes sense. How to implement the second as we can have many possibilities.

For each pair x, y you can write $$$n = 2^x 3^y + z$$$. The associated cost is $$$px + qy + rz$$$.

I was mistaken I didn't see the contraints

I guess you can simply use recursion. Just keeping check of the usage of +1/-1 will not give TLE. Something like this:

Intput -

2 100 100 1

Correct output - 2

Your output — 101

I can think of one improvement in your code $$$cost(n/2)+min(p,(n/2)*r)$$$ similarly for 3 case.

Yeah I think this will work. Didn't consider the case when r < p,q. Also I suppose memoization can help improve the efficiency.

Now your code reports 20 for this testcase:

While a lower cost 15 is possible by running 61 to 0 via doing

+1 +1 +1 /2 /2 /2 /2 -1 -1 -1 -1operations.In fact it can be done with cost 14: $$$0 \to 1 \to 2 \to 3 \to 4 \to 8 \to 16 \to 32 \to 31 \to 62 \to 61$$$.

You are right. But being pedantic, I didn't claim that 15 was the minimal possible cost. Just that the last rakeshpanda's solution wasn't good enough and I successfully "hacked" it.

Yeah this solution is horribly wrong. Don't think we can use recursion to solve this problem.

Your code never uses the "decrease by 1" operation?

Yeah you are correct. I didn't think of many test cases and also used a wrong assumption.

This problem was asked in previous Atcoder round. i am sharing the link below

Problem Link : Pay to Win

Editorial : this

Thanks a lot