2022 年 9 月青少年软编等考 C 语言三级真题解析

T1. 课程冲突

此题为 2021 年 9 月三级第一题原题，见 2021 年 9 月青少年软编等考 C 语言三级真题解析中的 T1。

T2. 42 点

$42$ 是：

• 组合数学上的第 $5$ 个卡特兰数
• 字符 '*' 的 $\mathtt{ASCII}$ 码
• 钼的原子序数
• $6$ 与 $9$ 的乘积结果的 $13$ 进制表示
• 生命、宇宙以及任何事情的终极答案
• 以及……表达式 $(1+5)/2\times (6-4)\times 7$ 的值

因此，小机器人 Marvin 发明了这个叫 $42$ 点的小游戏。在这个游戏中，玩家会获得 $n$ 个数。玩家需要使用 '+'、'-'、'*'、'/'、'('、')' 以及这 $n$ 个数构成一个合法的中缀表达式，并使得该表达式的值为 $42$。$n$ 个数之间的顺序可以改变。表达式运算过程中只能出现整数。

由于过于抑郁，Marvin 无力完成这个游戏，于是来找你帮忙。你的任务是对于给定的 $n$ 个数，判断他们是否能根据上述游戏规则算出 $42$。

时间限制：1 s
内存限制：64 MB

• 输入
  第一行为一个数 $n$，$1\le n\le 6$。
  第二行为 $n$ 个数，每个数均为 $[1,13]$ 范围内的整数。
• 输出
  输出一行，若可以算出 $42$ 则输出 YES，否则输出 NO（注意大小写）。
• 样例输入

  6
  1 5 2 6 4 7
  

• 样例输出

  YES
  

思路分析

此题考查搜索算法，有一定难度。思路类似于 2022 年 6 月第五题，见 2022 年 6 月青少年软编等考 C 语言三级真题解析中的 T5。

/*
 * Name: T2.cpp
 * Problem: 42 点
 * Author: Teacher Gao.
 * Date&Time: 2024/12/02 17:12
 */

#include <iostream>

using namespace std;

bool dfs(int a[], int n)
{
   
	if (n == 1)
		return a[n] == 42;

	int b[10];

	for (int i = 1; i < n; i++)
		for (int j = i+1; j <= n; j++) {
   
			int m = 1;
			for (int k = 1; k <= n; k++) {
   
				if (k != i && k != j)
					b[m++] = a[k];
			}

			b[m] = a[i] + a[j];
			if (dfs(b, m)) return 1;

			b[m] = a[i] - a[j];
			if (dfs(b, m)) return 1;

			b[m] = a[j] - a[i];
			if (dfs(b, m)) return 1;

			b[m] = a[i] * a[j];
			if (dfs(b, m)) return 1;

			if (a[i] % a[j] == 0) {