class Solution:

    def judgePoint24(self, cards: List[int]) -> bool: # 支持 n 个 卡的24点游戏
        size = len(cards)
        
        if len(cards) == 1:
            return abs(cards[0] - 24) < 0.0001

        for i in range(size):
            for j in range(size): #  挑选两个数
                if i == j: continue
                for sign in "+-*/":
                    newCards = cards[:]
                    newCards.remove(cards[i])
                    newCards.remove(cards[j]) # 取出来
                    try:
                        newCards.append(eval("%f%s%f" % (cards[i], sign, cards[j]))) # 加减乘除算一下放回去
                        if self.judgePoint24(newCards): # 递归调用
                            return True
                    except ZeroDivisionError:
                        pass
        return False

from typing import List


class Solution:
    def dfs(self, cards, formulas):
        size = len(cards)
        if len(cards) == 1:

            ans = abs(cards[0] - 24) < 0.0001
            if ans:
                print(formulas[0] + " = 24")
                return True

        for i in range(size):
            for j in range(size):
                if i == j: continue

                for sign in "+-*/":
                    newCards = cards[:]
                    newCards.remove(cards[i])
                    newCards.remove(cards[j])
                    newFormulas = formulas[:]
                    newFormulas.remove(formulas[i])
                    newFormulas.remove(formulas[j])
                    try:
                        formula = "%f%s%f" % (cards[i], sign, cards[j])
                        newCards.append(eval(formula))
                        newFormulas.append('(' + formulas[i] + sign + formulas[j] + ')')
                        if self.dfs(newCards, newFormulas):
                            return True

                    except ZeroDivisionError:
                        continue

        return False

    def judgePoint24(self, cards: List[int]) -> bool:
        return self.dfs(cards, list(map(str, cards)))


if __name__ == '__main__':
    sol = Solution()
    # cards = [4, 1, 8, 7]
    # cards = [1, 2, 1, 2]
    cards = [8, 1, 6, 6]
    ret = sol.judgePoint24(cards)
    print(ret)

# 输出

# (6/(1-(6/8))) = 24
# True

class ListNode:
    def __init__(self, key=0, val=0, prev=None, next=None):
        self.key = key
        self.val = val
        self.prev = prev
        self.next = next


class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.currentSize = 0
        self.dic = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key) -> int:
        if key in self.dic:
            self.move_to_end(key)
            return self.dic[key].val
        else:
            return -1

    def put(self, key, value: int) -> None:

        if self.capacity == 0: return

        if key in self.dic:  # 存在不用考虑size
            self.dic[key].val = value
            self.move_to_end(key)
        else:  # 不存在
            if self.currentSize == self.capacity:  # 满了
                self.delete(self.head.next.key)
                self.currentSize -= 1
            self.append(key, value)
            self.currentSize += 1

    def append(self, key, value: int) -> None:
        nodePrev = self.tail.prev
        nodeNext = self.tail

        node = ListNode(key, value, nodePrev, nodeNext)
        self.dic[key] = node

        nodePrev.next = node
        nodeNext.prev = node

    def delete(self, key) -> ListNode:
        node = self.dic.pop(key)

        nodePrev = node.prev
        nodeNext = node.next

        nodePrev.next = nodeNext
        nodeNext.prev = nodePrev

        return node

    def move_to_end(self, key) -> None:
        popped = self.delete(key)
        self.append(popped.key, popped.val)

from functools import wraps

# 自己定义一个lru装饰器
def lru_cache(size: [int, None] = 128):
    """
    size 如果是 None, 则缓存大小不受限制。但是递归深度python 是有限制的，
    使用这个装饰器并不能解决所有动态规划问题
    """
    if size is None:
        size = float('inf')

    def lru_cache_decorator(f):
        lru = LRUCache(size)

        @wraps(f)
        def decorated(*args, **kwargs):
            cached = lru.get(args)
            if cached == -1:
                ret = f(*args, **kwargs)
                lru.put(args, ret)
                return ret
            else:
                return cached

        return decorated

    return lru_cache_decorator

@lru_cache()
def feb(n):
    if n <= 1: return 1
    return feb(n - 1) + feb(n - 2)


if __name__ == '__main__':
    print(feb(1000)) # 跑起来飞快 去掉 装饰器慢如乌龟

# 写上 所有 化学元素和 原子序数的对应 。这里比较懒先写几个用得到的
DIC = {
    'H': 0,
    'He': 1,
    'Li': 2,
    'C': 5,
    'O': 7,
    'S': 15,
    'Al': 12,
    'Cu': 29,
}

RE_DIC = {
    0: 'H',
    1: 'He',
    2: 'Li',
    5: 'C',
    7: 'O',
    15: 'S',
    12: 'Al',
    29: 'Cu',
}


def solve(s):
    stack = [[0] * 100]  # 化学元素先设定一百个吧。每个栈帧是个数组 数组按照元素顺序存放着元素的出现次数
    n = len(s)
    for idx, item in enumerate(s):
        if item.isupper(): # 化学元素名字总是一个大写字母开头后面都是小写字母

            # 支持多字符的元素，识别出类似于 Al Cu 这样的元素
            end = idx + 1
            while end <= n - 1 and s[end].islower():
                end += 1
            name = s[idx:end]

            # 记录右下缀 ,如 读出 Al2 中数字 2
            times = 1
            if end <= n - 1 and s[end].isdecimal():
                times = int(s[end])
            stack[-1][DIC[name]] += times

        elif item == '(': # 压栈
            stack.append([0] * 100)

        elif item == ')': # 出栈
            times = 1
            if idx != n - 1 and s[idx + 1].isdecimal():  # 如果 ) 后面是数字 要加倍
                times = int(s[idx + 1])
            popped = stack.pop()
            # 把弹出的信息，合并到栈顶中去
            for i in range(len(popped)):
                stack[-1][i] += popped[i] * times

    return stack


if __name__ == '__main__':
    # s = "Al2(SO4)3"
    s = "Cu2(OH)2CO3"
    ret = solve(s)
    for i in range(100):
        if ret[0][i] != 0:
            print(f"原子{RE_DIC[i]} : {ret[0][i]}")

class Warrior:
    def __init__(self, a, d, c2, c3, c4):
        self.INITIAL_ATTACK = a  # 初始攻击力
        self.MAX_ATTACK_BUFF_TIME = c2  # 进攻buff 持续时间
        self.MAX_AIM_DEFENCE = d  # 目标最大防御力
        self.MAX_DEFENCE_BUFF_TIME = c3  # 减防buff持续时间
        self.PERMANENCY_ATTACK_INCREASE = c4  # 永久提升额

        self.baseAttack = self.INITIAL_ATTACK  # 基础攻击力
        self.aimDefence = self.MAX_AIM_DEFENCE  # 目标防御力
        self.defenceBuffTime = 0  # 减防buff剩余时间
        self.attackBuffTimes = []  # 攻击buff剩余时间

        self.totalAttack = 0

    def do1(self):
        # 进攻
        attack = (len(self.attackBuffTimes) + 1) * self.baseAttack  # 计算攻击力加成

        defence = self.MAX_AIM_DEFENCE
        if self.defenceBuffTime > 0:
            defence = 0

        self.totalAttack += max(1, attack - defence)
        self.final()

    def do2(self):
        # 增加buff
        self.attackBuffTimes.append(self.MAX_ATTACK_BUFF_TIME)
        self.final()

    def do3(self):
        # 刷新减防
        self.defenceBuffTime = self.MAX_DEFENCE_BUFF_TIME
        self.final()

    def do4(self):
        # 增加永久攻击
        self.baseAttack += self.PERMANENCY_ATTACK_INCREASE
        self.final()

    def final(self):
        # buff结算
        if 0 in self.attackBuffTimes: self.attackBuffTimes.remove(0)
        for i in range(len(self.attackBuffTimes)):
            self.attackBuffTimes[i] -= 1

        if self.defenceBuffTime != 0:
            self.defenceBuffTime -= 0


if __name__ == '__main__':
    a = 3
    d = 3
    c2 = 6
    c3 = 6
    c4 = 2
    opt = "121341"
    warrior = Warrior(a, d, c2, c3, c4)
    for c in opt:
        if c == '1':
            warrior.do1()
        elif c == '2':
            warrior.do2()
        elif c == '3':
            warrior.do3()
        elif c == '4':
            warrior.do4()
    print(warrior.totalAttack)
    # while True:
    #     try:
    #         n, a, d, c2, c3, c4 = [int(i) for i in input().split()]
    #         opt = input()
    #         ans = solve(a, d, c2, c3, c4, opt)
    #         print(ans)
    #     except:
    #         break

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        """XOR前缀和"""
        pre = [0]  # 前缀数组
        for i in range(len(arr)):
            pre.append(arr[i] ^ pre[-1])
        res = []
        for a, b in queries:
            res.append(pre[a] ^ pre[b + 1])

        return res

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        acc = list(accumulate([0] + arr, xor))
        return [acc[a] ^ acc[b + 1] for a, b in queries]

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        n = len(stones)

        @lru_cache(None)
        def recur(start, k):
            if start >= n - 1: return True
            for i in range(start + 1, n):
                if stones[start] + k - 1 == stones[i]:  # 往后遍历找到 能以 k-1 步跳到的石子
                    if recur(i, k - 1): return True
                if stones[start] + k == stones[i]:  # 往后遍历找到 能以 k 步跳到的石子
                    if recur(i, k): return True
                if stones[start] + k + 1 == stones[i]:  # 往后遍历找到 能以 k+1 步跳到的石子
                    if recur(i, k + 1): return True
                if stones[start] + k + 1 < stones[i]: break  # 因stones的单调性 提早结束遍历
            return False

        return recur(0, 0)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        res = []
        for x in nums:
            loc = bisect.bisect_left(res, x)
            if loc == len(res):
                res.append(x)
            else:
                res[loc] = x
        return len(res)