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;
}