"Mahit Gupta" <23*9*2*
5@s*u*e*t*u*a*e*u*a*> wrote:
> The way I thought of solving this problem was similar to the hints, take all the potions if the remaining hp after the potion is less than a sword. If it isn't skip the potion and take a sword. This doesn't seem to work as in some cases, taking lesser damage in the start is actually benificial.
> I don't understand how to interpret this in a greedy way, when to decide if taking a lower hit is better than a higher, I assumed taking a higher hit would always be better in the start and then take a lower one.
>
> 50 1 1 2
> 30
> 20
> That strategy doesn't seem to work as we would rather have a hit of just 15 in the beginning to get to 15 than to get a hit of 20 and then just get to 21
The trick to this problem is determining the optimum number of potions to take. We don't want to know whether taking the next potion does more damage than using the next sword. We rather want to know whether taking the next potion does more damage than using the final sword that would be used if we don't take this potion.
If the next potion does less damage, then the final sword (i.e. the weakest sword) that we would end up using if we don't take this potion, then stop taking potions and use all the swords.