Help in DP problem

Hi codechef community, Please help me with this problem

you are given x=1 and you have to make it n (given in input ) using one of the following operations and using minimum cost

operation 1 x = x+1 with cost1(input)
operation 2 x = x -1 with cost2(input)
operation 3 x = x * 2 with cost 3(input)

suppose n=8 , cost1=1 ,cost2=10 , cost3=100
then to reach 8 you should follow operation1 7 times thereby to reach 8 in minimum number of times.

What are the constraints on n ?

one thing I forgot mention
cost_of_doubling <= cost of incrementing<= cost_of_decrementing

and n<=100000

one more question if this order among between these costs is not given is the problme solvable at all ?

This condition is not satisfied in the example.
Also, source?

sorry please ignore the example

Can you provide link for the problem ?

1 Like

X-1 seems useless to me.
Just find number of ones in binary and find log.
~Log * cost3 + ones *cost1 something like that.
Edit: to be exact
\lfloor log_2(n)\rfloor * cost3 + (ones-1)*cost_1