总时间限制: 3000ms 内存限制: 65536kB

描述

给出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

思路

千里之行始于足下，我们要用 n 个数算24，必须先有2个数先算。这2个数算的结果，和剩下 n - 2 个数，就构成了 n - 1 个数求24的问题。

我们枚举穷举先算的2个数，以及这两个数的运算方式。

边界条件: 当 n = 1 时，如果计算结果为24，则输出 YES.

注意：浮点数的比较不能直接用 ==，而应当是两个数之差是不是小于某个很小的数的绝对值。

代码

#include <iostream>
#include <cmath>
using namespace std;
#define EPS 1e-6
double a[5];
bool isZero(double x) {
    return fabs(x) <= EPS;
}
bool count24(double a[], int n) { // 用数组a里的n个数计算24
    if( n == 1 ) {  // 到达边界
        if( isZero(a[0] - 24) )  return true;
        else  return false;
    }
    double b[5];
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {  // 枚举两个数的组合
            int remain = 0; // 还剩下remain个数, remain = n - 2
            for(int k = 0; k < n; k++) {
                if( k != i && k != j )
                    b[remain++] = a[k];  // 把其余的数放进b
            }
            // 枚举加减乘除各个情况
            b[remain] = a[i] + a[j];
            if( count24(b, remain + 1) )  return true;
            b[remain] = a[i] - a[j];
            if( count24(b, remain + 1) )  return true;
            b[remain] = a[j] - a[i];
            if( count24(b, remain + 1) )  return true;
            b[remain] = a[i] * a[j];
            if( count24(b, remain + 1) )  return true;
            if( !isZero(a[j]) ) {
                b[remain] = a[i] / a[j];
                if( count24(b, remain + 1) )  return true;
            }
            if( !isZero(a[i]) ) {
                b[remain] = a[j] / a[i];
                if( count24(b, remain + 1) )  return true;
            }
        }
    }
    return false;
}
int main() {
    while( cin >> a[0] >> a[1] >> a[2] >> a[3] ) {
        if(a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0)
            return 0;
        if( count24(a, 4) )
            cout << "YES" << endl;
        else 
            cout << "NO" << endl;
    }
    return 0;
}