• + 0 comments

    The problem statement might throw some people off (it did for me).

    Note: You don't need to face the mandragons in order. You can choose to face them in any order. Intuitively, you would choose to face them in increasing size of health (this is because if you choose to save and increase s, you would do so for smaller payout monsters that lead to bigger earnings later on.)

    def mandragora(H):
        H.sort()
        s = 1
        sumTail = sum(H)
        for i in range(0, len(H)):
            saveValue = (s+1)*(sumTail - H[i])
            eatValue = s*sumTail
            if saveValue > eatValue:
                s += 1
                sumTail -= H[i]
            else:
                return eatValue