02787: 算24

recursion, http://cs101.openjudge.cn/practice/02787

给出4个小于10个正整数，你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于24。

这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。

比如，对于5，5，5，1，我们知道5 * (5 – 1 / 5) = 24，因此可以得到24。又比如，对于1，1，4，2，我们怎么都不能得到24。

输入

输入数据包括多行，每行给出一组测试数据，包括4个小于10的正整数。最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。

输出

对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。

样例输入

5 5 5 1
1 1 4 2
0 0 0 0

样例输出

YES
NO

python

#gpt
'''
在这个优化的代码中，我们使用了递归和剪枝策略。首先按照题目的要求，输入的4个数字保持不变，
不进行排序。在每一次运算中，我们首先尝试加法和乘法，因为它们的运算结果更少受到数字大小的影响。
然后，我们根据数字的大小关系尝试减法和除法，只进行必要的组合运算，避免重复运算。

值得注意的是，这种优化策略可以减少冗余计算，但对于某些输入情况仍需要遍历所有可能的组合。
因此，在最坏情况下仍然可能需要较长的计算时间。
'''

def find(nums):
    if len(nums) == 1:
        return abs(nums[0] - 24) <= 0.000001

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            a = nums[i]
            b = nums[j]
            remaining_nums = []

            for k in range(len(nums)):
                if k != i and k != j:
                    remaining_nums.append(nums[k])

            # 尝试加法和乘法运算
            if find(remaining_nums + [a + b]) or find(remaining_nums + [a * b]):
                return True

            # 尝试减法运算
            if a > b and find(remaining_nums + [a - b]):
                return True
            if b > a and find(remaining_nums + [b - a]):
                return True

            # 尝试除法运算
            if b != 0 and find(remaining_nums + [a / b]):
                return True
            if a != 0 and find(remaining_nums + [b / a]):
                return True

    return False

while True:
    card = [int(x) for x in input().split()]
    if sum(card) == 0:
        break

    print("YES" if find(card) else "NO")

加速，打表

python

#gpt
'''
在这个优化的代码中，我们使用了递归和剪枝策略。首先按照题目的要求，输入的4个数字保持不变，
不进行排序。在每一次运算中，我们首先尝试加法和乘法，因为它们的运算结果更少受到数字大小的影响。
然后，我们根据数字的大小关系尝试减法和除法，只进行必要的组合运算，避免重复运算。

值得注意的是，这种优化策略可以减少冗余计算，但对于某些输入情况仍需要遍历所有可能的组合。
因此，在最坏情况下仍然可能需要较长的计算时间。
'''

from functools import lru_cache 

@lru_cache(maxsize = None)
def find(nums):
    if len(nums) == 1:
        return abs(nums[0] - 24) <= 0.000001

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            a = nums[i]
            b = nums[j]
            remaining_nums = []

            for k in range(len(nums)):
                if k != i and k != j:
                    remaining_nums.append(nums[k])

            # 尝试加法和乘法运算
            if find(tuple(remaining_nums + [a + b])) or find(tuple(remaining_nums + [a * b])):
                return True

            # 尝试减法运算
            if a > b and find(tuple(remaining_nums + [a - b])):
                return True
            if b > a and find(tuple(remaining_nums + [b - a])):
                return True

            # 尝试除法运算
            if b != 0 and find(tuple(remaining_nums + [a / b])):
                return True
            if a != 0 and find(tuple(remaining_nums + [b / a])):
                return True

    return False

while True:
    card = [int(x) for x in input().split()]
    if sum(card) == 0:
        break

    print("YES" if find(tuple(card)) else "NO")

python

# 马铉钦25化院

from itertools import permutations
from functools import lru_cache

sigs = ['+', '-', '*', '/']


def get_four(i):
    s = ''
    while i > 0:
        s += str(i % 4)
        i //= 4
    return '0' * (3 - len(s)) + s[::-1]


def jug(st):
    try:
        return 23.9 <= eval(st) <= 24.1
    except ArithmeticError:
        return False


@lru_cache(maxsize=None)
def sol(li):
    r = set(permutations(li))
    le = len(r)
    r = iter(r)
    coun = 0
    while coun < le:

        cou = 0
        nums = next(r)

        while cou < 64:

            indx = get_four(cou)
            sig = [sigs[int(indx[0])], sigs[int(indx[1])], sigs[int(indx[2])]]

            if jug(f'{nums[0]}{sig[0]}{nums[1]}{sig[1]}{nums[2]}{sig[2]}{nums[3]}') or jug(
                    f'({nums[0]}{sig[0]}{nums[1]}){sig[1]}{nums[2]}{sig[2]}{nums[3]}') or jug(
                    f'({nums[0]}{sig[0]}{nums[1]}{sig[1]}{nums[2]}){sig[2]}{nums[3]}') or jug(
                    f'{nums[0]}{sig[0]}({nums[1]}{sig[1]}{nums[2]}){sig[2]}{nums[3]}') or jug(
                    f'{nums[0]}{sig[0]}({nums[1]}{sig[1]}{nums[2]}{sig[2]}{nums[3]})') or jug(
                    f'({nums[0]}{sig[0]}{nums[1]}){sig[1]}({nums[2]}{sig[2]}{nums[3]})') or jug(
                    f'{nums[0]}{sig[0]}{nums[1]}{sig[1]}({nums[2]}{sig[2]}{nums[3]})') or jug(
                    f'{nums[0]}{sig[0]}(({nums[1]}{sig[1]}{nums[2]}){sig[2]}{nums[3]})') or jug(
                    f'({nums[0]}{sig[0]}({nums[1]}{sig[1]}{nums[2]})){sig[2]}{nums[3]}'):

                return True
            elif jug(f'(({nums[0]}{sig[0]}{nums[1]}){sig[1]}{nums[2]}){sig[2]}{nums[3]}') or jug(
                    f'{nums[0]}{sig[0]}({nums[1]}{sig[1]}({nums[2]}{sig[2]}{nums[3]}))'):
                return True
            cou += 1

        coun += 1
    return False


while True:
    li = tuple(sorted(list(map(int, input().split()))))
    if sum(li) == 0:
        break
    print('YES' if sol(li) else 'NO')

02787: 算24 ​

02787: 算24