YLT C++ 5级 2023.03

N3132 [CIE 202303 五级 T1] 拼点游戏

题目描述

$C$ 和 $S$ 两位同学一起玩拼点游戏。有一堆白色卡牌和一堆蓝色卡牌，每张卡牌上写了一个整数点数。
$C$ 随机抽取 $n$ 张白色卡牌，$S$ 随机抽取 $n$ 张蓝色卡牌，他们进行 $n$ 回合拼点，每次两人各出一张卡牌，点数大者获得三颗巧克力，小者获得一颗巧克力，如果点数相同，每人各得二颗巧克力，使用过的卡牌不得重复使用。
已知 $C$ 和 $S$ 取到的卡牌点数，请编程计算 $S$ 最多和最少能得到多少颗巧克力。

输入格式

输入包含多组测试数据
每组测试数据的第一行是一个整数 $n$ $(1 \le n \le 1000)$，
接下来一行是 $n$ 个整数，表示 $C$ 抽到的白色卡牌的点数，下一行也是 $n$ 个整数，表示 $S$ 抽到的蓝色卡牌的点数。
输入的最后以一个 $0$ 表示结束。

输出格式

对每组数据，输出一行，内容是两个整数用空格隔开，分别表示 $S$ 最多和最少可获得的巧克力数。

样例

样例 1
输入：

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

输出：

9 5
4 4
4 4

提示

暂无

N3050 [CIE 202303 五级 T2] 数字变换

题目描述

给定一个包含 $5$ 个数字 $(0-9)$ 的字符串，例如 02943，请将 12345 变换到它。 你可以采取 $3$ 种操作进行变换
$1$. 交换相邻的两个数字
$2$. 将一个数字加 $1$。如果加 $1$ 后大于 $9$，则变为 $0$
$3$. 将一个数字加倍。如果加倍后大于 $9$, 则将其变为加倍后的结果除以 $10$ 的余数。
最多只能用第 $2$ 种操作 $3$ 次，第 $3$ 种操作 $2$ 次 求最少经过多少次操作可以完成变换。

输入格式

有最多 $100,000$ 组数据 每组数据就是包含 $5$ 个数字的字符串

输出格式

对每组数据，输出将 $12345$ 变换到给定字符串所需要的最少操作步数。如果无法变换成功，输出 $-1$

样例

样例 1
输入：

12435
99999
12374

输出：

1
-1
3

提示

由于测试数据太多，如果对每组数据都从头进行搜索，就会超时。 建议先做预处理，即以12345 作为初始状态做一遍彻底的广搜，找出 12345 经合法变换能够到达的所有字符串，并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据，在上述预处理记录的结果中进行查询即可。

N3051 [CIE 202303 五级 T3] 打怪救公主

题目描述

公主被魔王抓起来关在了迷宫的某处，骑士想要拯救公主，也进入了迷宫。
但是魔王不会轻易让骑士拯救公主，魔王在迷宫中安排了许多怪兽。
每个怪兽都有血量，骑士也有初始血量，骑士打败怪兽后血量的减少量为怪物的血量值，血量减到 $0$，骑士会死去。
迷宫由 $m*n$ 个方块组成，每个方块有墙或者路或者怪物，骑士在其中一个方块上，他每个时间单位可以四个方向（上、下、左、右）走到相邻方格，若遇到怪物，必须打败怪物才能继续前进。
请帮忙判断骑士能否成功拯救公主，如果能，给出骑士还剩的最大血量。

输入格式

第一行为三个整数 $m$、$n$ 和 $t$，$t$ 表示骑士的初始血量。($m,n \leq 20$, $t \leq 30$)
第 $2$ 至 $m+1$ 行描述了迷宫，迷宫以 $m$ 行 $n$ 列的方格组成，
若方格为 . 则表示骑士可以通过，
若方格为 # 则表示墙，骑士不能通过，
若方格为数字则表示怪物，数字为怪物的血量，保证怪物的血量小于 $10$（一位数）。
* 表示了骑士当前所在的位置，+ 表示公主被囚禁的位置。

输出格式

若骑士能成功拯救公主，则输出骑士走到公主所囚禁方格所剩最大血量，否则输出 $0$。

样例

样例 1
输入：

5 6 10
..*...
.#2###
5#..4#
.##9.#
.#+..#

输出：

4

N3052 [CIE 202303 五级 T4] Freda的越野跑

题目描述

Freda 报名参加了学校的越野跑。越野跑共有 $N$ 人参加，在一条笔直的道路上进行。
这 $N$ 个人在起点处站成一列，相邻两个人之间保持一定的间距。
比赛开始后，这 $N$ 个人同时沿着道路向相同的方向跑去。
换句话说，这 $N$ 个人可以看作 $x$ 轴上的 $N$ 个点，在比赛开始后，它们同时向 $x$ 轴正方向移动。
假设越野跑的距离足够远，这 $N$ 个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？

输入格式

第一行 $1$ 个整数 $N$。
第二行为 $N$ 个非负整数，按从前到后的顺序给出每个人的跑步速度。
对于 $50\%$ 的数据，$2 \leq N \leq 1000$。
对于 $100\%$ 的数据，$2 \leq N \leq 100000$。

输出格式

一个整数，表示有多少对参赛者之间发生赶超事件。

样例

样例 1
输入：

5
1 3 10 8 5

输出：

7

提示

我们把这 $5$ 个人依次编号为 $A,B,C,D,E$，速度分别为 $1,3,10,8,5$。
在跑步过程中： $B,C,D,E$ 均会超过 $A$，因为他们的速度都比 $A$ 快；
$C,D,E$ 都会超过 $B$，因为他们的速度都比 $B$ 快；
$C,D,E$ 之间不会发生赶超，因为速度快的起跑时就在前边。