This question was interesting in the fact that just using any N-ary Search won’t be useful. Here the story goes. First thing that comes to our mind by seeing this questions is Binary Search, but that won’t fetch us an AC verdict. Next thing is to use Ternary Search but that also gives WA. Now we further improvise by using Quaternary Search but in vain. Lastly we code up a 5-ary Search solution that gets us most of the tasks correct but we miss an AC verdict by some 3-4 odd tasks.
In this whole story we forgot that most undermined searching algorithm Linear Search also has a role to play. This is because in worst case we can afford only atmost 6 repairing operations (with c = 150 and fixed budget of 1000). Unfortunately, our any N-ary solution is going to take more than these because of the diminishing range. So the remedy is to use linear search from lower voltage to a higher voltage whenever our remaining budget permits this because it is much cheaper to test the panel with a lower voltage than a higher voltage which breaks it (as we have to repair after failure). The pseudo code is :-
if ( ( high - low + 1 + c) <= budget) { linear search } else { 5-ary search } }. One more thing, in 5-ary search we will get 4 intermediate points in between our boundaries. So always start checking for valid range by left most intermediate point to 4th one, this again because of economic reasons.
Yup it is true through my experience that we have to use atleast 5-ary Search along with Budget Permissible Linear Search to get an AC verdict in this problem.
Here is the link to my solution - https://www.codechef.com/viewsolution/21877513