1
class Solution:
2
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
3

4
        @cache
5
        def fn(lo, hi):
6
            """Return possible answers of s[lo:hi]."""
7
            if lo + 1 == hi:
8
                return {int(s[lo])}
9
            ans = set()
10
            for mid in range(lo + 1, hi, 2):
11
                for x in fn(lo, mid):
12
                    for y in fn(mid + 1, hi):
13
                        if s[mid] == "+" and x + y <= 1000:
14
                            ans.add(x + y)
15
                        elif s[mid] == "*" and x * y <= 1000:
16
                            ans.add(x * y)
17
            return ans
18

19
        target = eval(s)
20
        cand = fn(0, len(s))
21
        ans = 0
22
        for x in answers:
23
            if x == target:
24
                ans += 5
25
            elif x in cand:
26
                ans += 2
27
        return ans