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)
e.g
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 ?
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