Skip to content

14016: 【原4016】24点游戏

题目

题目描述

author: Naive Yan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4016

Description

24点游戏是一个非常有意思的游戏,很流行,玩法很简单:给你 4张牌,每张牌上有数字(其中A 代表1,J 代表11,Q 代表 12,K代表13),你可以利用数学中的加、减、乘、除以及括号想办法得到24。例如:((AK)-J)Q 等价于((113)-11)12=24。 加减乘不用多说了,但除法必须满足能整除才能除!这样有一些是得不到 24 点的,所以这里只要求求出不超过24的最大值。

Input Format

输入第一行 N (1<=N<=5),表示有 N 组测试数据。

每组测试数据输入4行,每行一个整数 (1 到 13) 表示牌值。

Output Format

每组测试数据输出一行仅一个整数,表示所能得到的最大的不超过24的值。

Sample Input

3
3
3
3
3
1
1
1
1
12
5
13
1

Sample Output

24
4
21

q4x3's solution

/**
 * 模拟
 * 算24点,不超过24的最大结果
 * 屎山,注意细节处理即可
 **/
#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    int a[4];
    for(int n = 0;n < N;++ n) {
        int ans = 0;
        cin >> a[0] >> a[1] >> a[2] >> a[3];
        for(int i = 0;i < 4;++ i)
            for(int j = 0;j < 4;++ j) {
                if(j == i) continue;
                int tmp1[5] = {0};
                tmp1[0] = a[i] + a[j];
                tmp1[1] = a[i] - a[j];
                tmp1[2] = a[j] - a[i];
                tmp1[3] = a[i] * a[j];
                if(a[i] % a[j] == 0) tmp1[4] = a[i] / a[j];
                if(a[j] % a[i] == 0) tmp1[4] = a[j] / a[i];
                for(int k = 0;k < 4 + 1 * (tmp1[4] != 0);++ k)
                    for(int p = 0;p < 4;++ p) {
                        if((p == i)||(p == j)) continue;
                        int tmp2[5] = {0};
                        tmp2[0] = tmp1[k] + a[p];
                        tmp2[1] = tmp1[k] - a[p];
                        tmp2[2] = a[p] - tmp1[k];
                        tmp2[3] = tmp1[k] * a[p];
                        if(a[p] != 0 && tmp1[k] % a[p] == 0) tmp2[4] = tmp1[k] / a[p];
                        if(tmp1[k] != 0 && a[p] % tmp1[k] == 0) tmp2[4] = a[p] / tmp1[k];
                        for(int t = 0;t < 4 + 1 * (tmp2[4] != 0);++ t)
                            for(int q = 0;q < 4;++ q) {
                                if((q == i)||(q == j)||(q == p)) continue;
                                int tmp3[5] = {0};
                                tmp3[0] = tmp2[t] + a[q];
                                tmp3[1] = tmp2[t] - a[q];
                                tmp3[2] = a[q] - tmp2[t];
                                tmp3[3] = tmp2[t] * a[q];
                                if(a[q] != 0 && tmp2[t] % a[q] == 0) tmp3[4] = tmp2[t] / a[q];
                                if(tmp2[t] != 0 && a[q] % tmp2[t] == 0) tmp3[4] = a[q] / tmp2[t];
                                for(int b = 0;b < 5;++ b)
                                    if(tmp3[b] <= 24 && ans < tmp3[b]) ans = tmp3[b];
                            }
                    }
                for(int c = 0;c < 4;++ c) {
                    if((c == i)||(c == j)) continue;
                    for(int d = 0;d < 4;++ d) {
                        if((d == i)||(d == j)||(d == c)) continue;
                        int tmp4[5] = {0};
                        tmp4[0] = a[c] + a[d];
                        tmp4[1] = a[c] - a[d];
                        tmp4[2] = a[d] - a[c];
                        tmp4[3] = a[c] * a[d];
                        if(a[c] % a[d] == 0) tmp4[4] = a[c] / a[d];
                        if(a[d] % a[c] == 0) tmp4[4] = a[d] / a[c];
                        for(int e = 0;e < 4 + 1 * (tmp4[4] != 0);++ e)
                            for(int f = 0;f < 4 + 1 * (tmp1[4] != 0);++ f) {
                                int tmp5[5];
                                tmp5[0] = tmp4[e] + tmp1[f];
                                tmp5[1] = tmp4[e] - tmp1[f];
                                tmp5[2] = tmp1[f] - tmp4[e];
                                tmp5[3] = tmp4[e] * tmp1[f];
                                if(tmp4[e] != 0 && tmp1[f] % tmp4[e] == 0) tmp5[4] = tmp1[f] / tmp4[e];
                                if(tmp1[f] != 0 && tmp4[e] % tmp1[f] == 0) tmp5[4] = tmp4[e] / tmp1[f];
                                for(int g = 0;g < 5;++ g)
                                    if(tmp5[g] <= 24 && ans < tmp5[g]) ans = tmp5[g];
                            }
                    }
                }
            }
            cout << ans << endl;
        }
}

victrid's solution

#include <iostream>
//! Ugly
using namespace std;
int maxnum = -1000;
int inline maxi(int a, int b) { return a > b ? a : b; }
int inline mini(int a) { return a <= 24 ? a : -1000; }
int polirovat(int a, int b, int calctype) {
    switch (calctype) {
    case 0:
        return a + b;
    case 1:
        return a - b;
    case 2:
        return a * b;
    case 3:
        return a / b;
    case 4:
        return b - a;
    case 5:
        return b / a;
    }
    return 0;
}
int summation(int c1) {
    maxnum = maxi(mini(c1), maxnum);
    return maxnum;
}
int maxa(int c1, int c2) {
    for (int i = 0; i < 6; i++)
        if ((i != 3 && i != 5) || (c2 != 0 && i == 3 && (!(c1 % c2))) || (c1 != 0 && i == 5 && (!(c2 % c1))))
            summation(polirovat(c1, c2, i));
    return maxnum;
}
int maxa(int c1, int c2, int c3) {
    for (int i = 0; i < 6; i++) {
        if ((i != 3 && i != 5) || (c2 != 0 && i == 3 && (!(c1 % c2))) || (c1 != 0 && i == 5 && (!(c2 % c1))))
            summation(maxa(polirovat(c1, c2, i), c3));
        if ((i != 3 && i != 5) || (c3 != 0 && i == 3 && (!(c1 % c3))) || (c1 != 0 && i == 5 && (!(c3 % c1))))
            summation(maxa(polirovat(c1, c3, i), c2));
        if ((i != 3 && i != 5) || (c3 != 0 && i == 3 && (!(c2 % c3))) || (c2 != 0 && i == 5 && (!(c3 % c2))))
            summation(maxa(polirovat(c2, c3, i), c1));
    }
    return maxnum;
}
int maxa(int c1, int c2, int c3, int c4) {
    for (int i = 0; i < 6; i++) {
        if ((i != 3 && i != 5) || (c2 != 0 && i == 3 && (!(c1 % c2))) || (c1 != 0 && i == 5 && (!(c2 % c1))))
            summation(maxa(polirovat(c1, c2, i), c3, c4));
        if ((i != 3 && i != 5) || (c3 != 0 && i == 3 && (!(c1 % c3))) || (c1 != 0 && i == 5 && (!(c3 % c1))))
            summation(maxa(polirovat(c1, c3, i), c2, c4));
        if ((i != 3 && i != 5) || (c3 != 0 && i == 3 && (!(c2 % c3))) || (c2 != 0 && i == 5 && (!(c3 % c2))))
            summation(maxa(polirovat(c2, c3, i), c1, c4));
        if ((i != 3 && i != 5) || (c4 != 0 && i == 3 && (!(c1 % c4))) || (c1 != 0 && i == 5 && (!(c4 % c1))))
            summation(maxa(polirovat(c1, c4, i), c3, c2));
        if ((i != 3 && i != 5) || (c4 != 0 && i == 3 && (!(c2 % c4))) || (c2 != 0 && i == 5 && (!(c4 % c2))))
            summation(maxa(polirovat(c2, c4, i), c1, c3));
        if ((i != 3 && i != 5) || (c4 != 0 && i == 3 && (!(c3 % c4))) || (c3 != 0 && i == 5 && (!(c4 % c3))))
            summation(maxa(polirovat(c3, c4, i), c1, c2));
        for (int j = 0; j < 6; j++) {
            if (((i != 3 && i != 5) || (c2 != 0 && i == 3 && (!(c1 % c2))) ||
                 (c1 != 0 && i == 5 && (!(c2 % c1)))) &&
                ((j != 3 && j != 5) || (c4 != 0 && j == 3 && (!(c3 % c4))) || (c3 != 0 && j == 5 && (!(c4 % c3)))))
                summation(maxa(polirovat(c1, c2, i), polirovat(c3, c4, j)));
            if (((i != 3 && i != 5) || (c3 != 0 && i == 3 && (!(c2 % c3))) ||
                 (c2 != 0 && i == 5 && (!(c3 % c2)))) &&
                ((j != 3 && j != 5) || (c4 != 0 && j == 3 && (!(c1 % c4))) || (c1 != 0 && j == 5 && (!(c4 % c1)))))
                summation(maxa(polirovat(c2, c3, i), polirovat(c1, c4, j)));
            if (((i != 3 && i != 5) || (c4 != 0 && i == 3 && (!(c2 % c4))) ||
                 (c2 != 0 && i == 5 && (!(c4 % c2)))) &&
                ((j != 3 && j != 5) || (c3 != 0 && j == 3 && (!(c1 % c3))) || (c1 != 0 && j == 5 && (!(c3 % c1)))))
                summation(maxa(polirovat(c2, c4, i), polirovat(c1, c3, j)));
        }
    }
    return maxnum;
}
int main() {
    int N, c1, c2, c3, c4;
    cin >> N;
    int* s = new int[N];
    for (int i = 0; i < N; i++) {
        cin >> c1 >> c2 >> c3 >> c4;
        s[i]   = maxa(c1, c2, c3, c4);
        maxnum = -1000;
    }
    for (int i = 0; i < N; i++) {
        if (i)
            cout << endl;
        cout << s[i];
    }
    // int z = 0;
    // for (int c1 = 1; c1 < 14; c1++)
    //     for (int c2 = c1; c2 < 14; c2++)
    //         for (int c3 = c2; c3 < 14; c3++) {
    //             for (int c4 = c3; c4 < 14; c4++) {
    //                 z += !(maxa(c1, c2, c3, c4) == 24);
    //                 maxnum = -1000;
    //             }
    //         }
    // cout << z;
}