#3861. 算24(C++三级)

算24(C++三级)

题目描述

描述 给出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 1 2 3

样例输出

YES NO 1 2

分析

​ 题目的意思,随便使用括号,意思就是运算顺序随便我们如何组合。

​ 这个本质上还是需要使用递归遍历+分解的做法。从4个数中选取两个数进行某种运算,然后把得到的数与剩下的两个数组合成一个3个数的数组,在这个数组中算24,最后分解为对1个数组算24的情况。

​ 这里还发现了一个好玩的情况,如果我们的bool函数最后不return false,它就会自动结束,然后返回true。

Limitation

1s, 1024KiB for each test case.