Description

为了培养小孩的计算能力, 大人们经常给小孩玩这样的游戏: 从 1 付扑克牌中任意抽出 4 张扑克, 要小孩用 +,-,*,/ 和括号组成一个合法的表达式, 并使表达式的值为 24 点. 这种游戏就是所谓的 “24 点游戏”“. 请你编程求出对于给出的任意 \(4\) 个正整数 \(a, b, c, d\) 能组成多少个值为 \(24\) 的不同表达式.

Input

输入共一行, 为 \(4\) 个正整数 \(a, b, c, d (0 \leq a, b, c, d \leq 100)\)

Output

输出由 \(a, b, c, d\) 组成的值为 \(24\) 的表达式的个数, 如没有, 输出 \(0\).

Sample Input

5 5 5 5

Sample Output

1

Explanation

如果了解了表达式树是什么就不会慌神了 (虽然我知道表达式树是什么)

就是枚举一下运算符的优先级, 然后计算表达式值, 检验是否为 \(24\), 然后轻轻松松就可 搞定一个 hash 存贮这个表达式, 最后判重一下即可 (其实也没判重, 因为本来并没有重, 说的人多了, 也便成了判重)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 8010;
const llf epsilon = 1e-5;

int res_hash[maxn], res_hash_cnt = 0;
int val[4], rank[4];
void submit_result(int _1, int _2, int _3, int _4, int _5, int _6, int _7) {
    res_hash[++res_hash_cnt] =
        (_1<<0) | (_2<<3) | (_3<<6) | (_4<<9) | (_5<<12) | (_6<<15) | (_7<<18);
    return ; }
llf lam(llf a, llf b, int op) { // Lambda operation
    switch (op) {
        // In the case we don't use 1-4 is because it costs more space to store hash
        case 0: return a+b;
        case 1: return a-b;
        case 2: return a*b;
        case 3: return a/b;
    } return a; }
bool priority(int o_1, int o_2) { // o_2 prioritized over o_1 as an operator
    if (o_1 == 0) return o_2 > 1;
    if (o_1 == 2) return o_2 < 2;
    return true; }
bool match(llf inp) {
    return fabs(inp - 24.0) < epsilon; }

void judge(int v_1, int v_2, int v_3, int v_4)
{
    rep(o_1, 0, 3) rep(o_2, 0, 3) rep(o_3, 0, 3) {
        bool p_1 = priority(o_3, o_2),
             p_2 = priority(o_2, o_1);
        // Yet a lazy macro function to reduce burden
        #define update(_prej,_expr,_1,_2,_3,_4,_5,_6,_7)\
            if((_prej)&&match(_expr)) submit_result(_1,_2,_3,_4,_5,_6,_7);
        // Yet another set of lazy stuff
        int _1 = rank[v_1], _2 = rank[v_2], _3 = rank[v_3], _4 = rank[v_4],
            _5 = o_1 + 4,   _6 = o_2 + 4,   _7 = o_3 + 4;
        // Here it comes... the big bulk of code
        update(true, lam( lam( lam( val[v_1], val[v_2], o_1 ), val[v_3], o_2 ), val[v_4], o_3 ),
            _1, _2, _5, _3, _6, _4, _7);
        update(p_1, lam( lam( val[v_1], val[v_2], o_1 ), lam( val[v_3], val[v_4], o_2 ), o_3 ),
            _1, _2, _5, _3, _4, _6, _7);
        update(p_2, lam( lam( val[v_1], lam( val[v_2], val[v_3], o_1 ), o_2 ), val[v_4], o_3 ),
            _1, _2, _3, _5, _6, _4, _7);
        update(p_1, lam( val[v_1], lam( lam( val[v_2], val[v_3], o_1 ), val[v_4], o_2 ), o_3 ),
            _1, _2, _3, _5, _4, _6, _7);
        update(p_1 && p_2, lam( val[v_1], lam( val[v_2], lam( val[v_3], val[v_4], o_1 ), o_2 ), o_3 ),
            _1, _2, _3, _4, _5, _6, _7);
        // Finally over...
        continue;
    }
    return ;
}

int main(int argc, char** argv)
{
    for (int i = 1; i <= 4; i++)
        scanf("%d", &val[i-1]);
    // Getting rank (in an O(n^2) way)
    rep(i, 0, 3) rep(j, 0, 3) if (i != j)
        rank[i] += val[i] < val[j];
    // Checking all possibilities
    rep(_1, 0, 3) rep(_2, 0, 3) rep(_3, 0, 3) rep(_4, 0, 3)
        if (_1!=_2 && _1!=_3 && _1!=_4 && _2!=_3 && _2!=_4 && _3!=_4) {
            // Ready to judge with this tuple
            judge(_1, _2, _3, _4);
        }
    // Retrieving result
    sort(res_hash + 1, res_hash + 1 + res_hash_cnt);
    int res = 0;
    for (int i = 1; i <= res_hash_cnt; i++)
        res += res_hash[i] != res_hash[i-1];
    printf("%d\n", res);
    return 0;
}