808. Soup Servings

link

So this is a very tricky question. First in mind would be backtrack and dp.

However the dataset is 10^9, it should be solved in O(lng n) time.

Answers within 10-5 of the actual answer will be accepted. <==== it means it can accept relative error

class Solution:
    def soupServings(self, n: int) -> float:

        @cache
        def backtrack(left, right):
            if left <= 0 and right <= 0:
                return 0.5
            if left <= 0:
                return 1
            if right <= 0:
                return 0

            res = sum([
                backtrack(left-100, right),
                backtrack(left-75, right-25),
                backtrack(left-50, right-50),
                backtrack(left-25, right-75),
            ])

            return res / 4

        # trick part
        i = 100

        while 1 - backtrack(i, i) > 10 ** -6:
            i += 100

        if n < i:
            return backtrack(n, n)

        return 1.0