ISSUE : I proposed a logic for this question which works fine on paper but i did some blunder in my code because of i m getting wrong answers. I m unable to find mistakes in my code. Kindly help !!!
Can anyone help me figure out why my code is not giving correct output ?
My solution link - https://www.codechef.com/viewsolution/35869168
my logic - i have created a multiset storing poppulations of every country in ascending order.
- At any day (be it the first day of curing) if the number of cures available, X,
is equal or greater than the largest element in multiset (country with the largest population) then the answer will be size of the multiset (as if we start from the last we can cure each country in one day) - IF X is less than last element of multiset then arises two cases :
A) if its the first day of curing - then simply use X to cure the country with highest population (last element of set), no need to update X (X remains same for the next day) and then update the countries population (after doubling) on which we used X cures. and we increment the tally of total days required by one.
B) else (when its not first day) - then we further check a condition hence two cases arise -
a) we will search for a element in multiset within the range [x,2x] inclusively
if a value found then we will use as many cures as the value of element returned
i.e size of population found within range [x,2x] let that population be P,
thus X = P (updating X for next day) and we remove that element from multiset
(because this country will be country cured on that day) and we increment the
total days required by one.
b) else (when no such value in multiset exits in range [x,2x] ) then again we will
go to cure the country with largest population present. X will be updated to 2*X
(because today we can use 2*X cures to cure the most populated country), thus
X = X*2, we also update the population of that country after doubling at end of
the day.
Note : Also before doing all these tasks i also check whether my multiset is empty or not.
I have also attached explanation with sample test-cases.
Testcase 1 :
when X = 1, N =5 and country’s populations are 10, 20, 30, 40, 50
Testcase 2 :
when X = 10, N = 3 and country’s populations are 1, 20, 110
PLZ read this and help me out with my logic (which works on paper but i m failing to write as a whole code) and piece of code .