 # MAXEP: Changing ratio in every iteration

I know that we can divide the entire range [1,N] into some appropriate ‘x’ number of blocks and solve it.

I am trying to solve the problem by binary search only (without linear search) by changing the ratio in every iteration. I am getting only 25 points by implementing the above idea.

Can someone please have a look at my code ? I have included comments wherever necessary.
Submission:-https://www.codechef.com/viewsolution/22016656

Thanks.

Your code fails because you are running out of coins. The first test case that fails is 1000 150 with the answer as 1 (the x required) (or something similar), your code asks the grader 6+ questions whose answer is 1 (i.e. the circuit breaks) so after resetting the circuit you get 150(7+) + (7+) coins > 1000 (max allotted) so the grader responds with a -1 and you get the WA.*

Reconsidering the proper ranges will help.

P.S.: I tested your code with 1000 150 and x as 1 and it throws a Division by Zero Exception.

The number of coins = 1000. Now consider the cost to repair is 150(max constraint). This means at max only 6 times we can repair the panel. N(max)=150,000. Now what if we use binary search. To find answer it will take at most log(150000)base 2 = 17 steps. Consider that answer is integer 1 , then you will find that 17*150 is the cost , which is greater than 1000. So to get answer take log(150000)base 8 which is less than 6. Just do binary search , but take mid = start+(end-start)/8; print out end , and you will get all points. We can prove that log base 8 actually solves the problem in at most 6 steps. It is guaranteed that it will get 1 as grader output at most 6 times, and I think this is optimal. There are many methods to solve but this was binary search style approach.

My code is provided.