YLT C++ 3级 2025.03

N5648 [CIE 202503 三级 T1] 分组均衡性

题目描述

在上机实验课上，老师将所有学生排列为 $n$ 排，每排坐 $m$ 个学生。每个学生有左右两个邻座（除了这一排的左右两端）。每个人可以和自己的邻座互相帮助完成实验。除了每排左右两端的学生，中间的每个学生都可以同时与两个邻座分别协作。
由于每个学生的个人能力不同，假设协作产生的小组能力值是两个协作学生的能力值之和，老师希望知道，自己给出的座位安排在多大程度上是“均衡”的 —— 所谓分组均衡性，是指所有可能组成的协作小组的能力值的最大值与最小值之差。
给定一张座位安排表，请计算这个安排的分组均衡性。

输入格式

输入第一行给出 $2$ 个正整数 $n$ 和 $m$（$2 \le n, m \le 100$），依次为座位的排数和每排的人数。
随后 $n$ 行，每行给出 $m$ 个数字，代表对应座位上学生的能力值（为区间 $[1, 100]$ 内的整数）。同行数字间以空格分隔。

输出格式

在一行中输出分组均衡性。

样例

样例 1
输入：

3 5
10 80 30 95 60
79 55 63 84 41
98 23 72 85 58

输出：

67

提示

样例解释：最强组合是第 $3$ 排的 $72+85=157$；最弱组合是第 $1$ 排的 $10+80=90$。因此两者之差为 $67$。

N5649 [CIE 202503 三级 T2] 狼人杀简单版

题目描述

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，$1$ 号玩家说：“$2$ 号是狼人”，$2$ 号玩家说：“$3$ 号是好人”，$3$ 号玩家说：“$4$ 号是狼人”，$4$ 号玩家说：“$5$ 号是好人”，$5$ 号玩家说：“$4$ 号是好人”。已知这 $5$ 名玩家中有 $2$ 人扮演狼人角色，有 $2$ 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？
本题是这个问题的升级版：已知 $n$ 名玩家中有 $2$ 人扮演狼人角色，有 $2$ 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？

输入格式

输入在第一行中给出一个正整数 $n$（$5 \le n \le 100$）。
随后 $n$ 行，第 $i$ 行给出第 $i$ 号玩家说的话（$1 \le i \le n$)，即一个玩家编号，用正号表示好人，负号表示狼人。

输出格式

如果有解，在一行中按递增顺序输出 $2$ 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 $A = \{a[1], \ldots, a[M]\}$ 和 $B = \{b[1], \ldots, b[M]\}$，若存在 $0 \le k < M$ 使得 $a[i]=b[i]$（$i \le k$)，且 $a[k+1] < b[k+1]$，则称序列 $A$ 小于序列 $B$。若无解则输出 No Solution。

样例

样例 1
输入：

5
-2
+3
-4
+5
+4

输出：

1 4

样例 2
输入：

6
+6
+3
+1
-5
-2
+4

输出：

1 5

样例 3
输入：

5
-2
-3
-4
-5
-1

输出：

No Solution

N5650 [CIE 202503 三级 T3] 身高均衡排列问题

题目描述

在一个需要排列的队列中，个体存在「视觉高度敏感」
特性：当且仅当一个人直接看到其相邻的人比自己高时，会使用增高装置提升自身高度。每个个体使用的增高层数必须严格超过相邻较高者的总高度（自身身高 + 已使用的增高层数）。
给定初始队列的身高数据，计算最终使用增高层数最多的个体及其使用的层数。

输入格式

第一行包含一个正整数 $n(1 \leq n \leq 10^4)$，表示队列中的人数。
第二行包含 $n$ 个正整数 $h_1, h_2, \ldots, h_n(1 \leq h_i \leq 300)$，表示每个人的初始身高（单位：厘米）,数字间以空格分隔。

输出格式

输出所有使用最多增高层数的个体信息，按从左到右的顺序排列。每行包含两个整数，分别表示个体在队列中的位置（从 $1$ 开始）和使用的增高层数。如果有并列，按从左到右的顺序，每个人的信息占一行。

样例

样例 1
输入：

10
150 160 186 200 170 175 180 186 186 183

输出：

1 3
5 3

N5651 [CIE 202503 三级 T4] 分玩具

题目描述

已知 $n$ 位小朋友对 $m$ 件玩具的喜好（$n \le m$），现要将 $m$ 件玩具分给 $n$ 位小朋友，每位小朋友只能分到 $1$ 件玩具，每件玩具也最多只能分给 $1$ 位小朋友，并且还要求每位小朋友都能分到自己喜欢的玩具。
本题请你对任意 $n$ 和 $m$ 尝试列出所有满足要求的方案。

输入格式

输入第一行给出两个正整数 $n$ 和 $m$（$n \le m \le 8$），即小朋友人数和玩具的数量。
随后 $n$ 行，每行给出 $m$ 个数字。其中第 $i$ 行第 $j$ 个数字为 $1$ 表示第 $i$ 位小朋友喜欢第 $j$ 件玩具，为 $0$ 则表示不喜欢。

输出格式

按升序列出所有满足要求的方案，格式为 $(s_1, \ldots, s_n)$。其中 $s_i$ 表示第 $i$ 位小朋友分到了第 $s_i$ 件玩具。
注：方案 $(a_1, \ldots, a_n) < (b_1, \ldots, b_n)$ 是指存在 $1 \le k \le n$，使得 $a_i = b_i$ 对所有 $1 \le i < k$ 成立，并且有 $a_k < b_k$。

样例

样例 1
输入：

4 5
0 1 0 0 1
1 1 0 1 0
1 0 1 1 0
0 0 0 1 1

输出：

(2,1,3,4)
(2,1,3,5)
(2,1,4,5)
(2,4,1,5)
(2,4,3,5)
(5,1,3,4)
(5,2,1,4)
(5,2,3,4)