题目类型说明

这是一道提交函数题 / 多进程交互库调用题。你需要实现题目要求的函数，由评测程序在不同进程中调用。

你需要实现两个函数：

int giveHint(int N, int M, int H, std::vector<int> cards);

void playGame(
    int N,
    int M,
    int H,
    int playerIndex,
    std::vector<int> cards,
    int hint,
    std::vector<int> earlierPlaced
);

评测程序还会提供以下接口供 playGame 调用：

std::vector<int> passTurn();
void placeCard();

---

题目描述

Klimi 邀请了 N 位朋友来体验她新设计的一款卡牌游戏，朋友们按编号 $0,1,\dots,N-1$ 围坐在一张圆桌旁。

游戏开始时，每位玩家都会抽到一张写有整数的卡牌，数值范围在区间

$$[0,\ M-1]$$

内。卡牌会被放在玩家额头上，因此：

• 每位玩家都能看到其他所有玩家的卡牌；
• 但看不到自己的卡牌。

牌堆中每个数值的卡牌数量都无限，因此允许多位玩家抽到相同的数值。

游戏过程中，玩家之间不能以任何方式通信。

---

游戏规则

游戏按**轮（round）**进行。每一轮中，仍未出牌的玩家按照编号从小到大的顺序依次行动。

当某位仍在游戏中的玩家行动时，他有两种选择：

1. Pass：本轮不做任何操作；
2. Place card：把自己的卡牌放到桌上，并从此退出游戏。

如果某位玩家已经放下了卡牌，那么之后的轮次中会跳过他的行动。

游戏会持续若干轮，直到所有玩家都把卡牌放到桌上。

游戏的目标是：桌上的卡牌按非递减顺序出现。

---

Klimi 的提示

由于这是朋友们第一次玩这款游戏，Klimi 担心他们太难获胜。因此，在所有人抽牌完成后，Klimi 会看到所有玩家的卡牌，然后公开说出一个提示。这个提示只能是一个整数，范围为：

$$[0,\ H-1]$$

此外，Klimi 希望早点睡觉，所以整局游戏不能超过 $R_{\max}$ 轮。具体取值见后文的“子任务”和“评分方式”。

你的任务是为：

• Klimi 设计生成提示的方法；
• 为所有玩家设计出牌策略，

使得游戏在限制内成功完成。

---

实现细节

你需要实现两个函数。

1. giveHint

int giveHint(int N, int M, int H, std::vector<int> cards);

该函数表示 Klimi 的行为，负责生成公开提示。

参数说明：

• N、M、H：题目中给定的参数；
• cards[i]：第 i 位玩家抽到的卡牌数值。

返回值必须在区间

$$[0,\ H-1]$$

内。

---

2. playGame

void playGame(
    int N,
    int M,
    int H,
    int playerIndex,
    std::vector<int> cards,
    int hint,
    std::vector<int> earlierPlaced
);

该函数表示某个玩家视角下的策略。

参数说明：

• N、M、H：题目中给定的参数；
• playerIndex：当前玩家编号；
• cards：所有玩家的卡牌信息。
  • 对于 $i \ne \text{playerIndex}$，cards[i] 等于第 i 位玩家的卡牌值；
  • 对于当前玩家本人，有 cards[playerIndex] = -1；
• hint：giveHint 生成的提示；
• earlierPlaced：在第一轮中，编号比 playerIndex 小、并且已经放下卡牌的玩家编号列表。

在 playGame 中，玩家必须通过 grader 提供的接口进行行动。

如果当前玩家选择继续等待，应调用：

std::vector<int> passTurn();

这会让系统继续模拟其他玩家的行动，直到下一轮该玩家再次轮到行动时才返回。返回值为：在这段时间内已经放下卡牌的玩家编号列表。

如果当前玩家决定出牌，应调用：

void placeCard();

调用 placeCard() 之后，你的程序：

• 不得再调用 grader 中的其他函数；
• 必须正常从 playGame 返回。

---

评测方式

对每个测试，评测程序会：

• 启动 1 个进程调用 giveHint；
• 再启动 N 个不同进程，分别调用每位玩家对应的 playGame。

所有玩家进程是并行执行的。

评测时，程序总耗时与总内存消耗，按所有这些进程的资源使用总和计算。

你的程序必须：

• 包含头文件 cardgame.h；
• 不得实现 main 函数；
• 不得使用标准输入输出进行交互。

---

评分与违规情况

设当前子任务的提示范围上界为 $H$，最大允许轮数为 $R_{\max}$。

若某个测试中发生以下任一情况，则该测试所在子任务得 0 分：

• 你返回的提示不在区间 $[0,\ H-1]$ 内；
• 游戏没有在 $R_{\max}$ 轮之内结束；
• 卡牌放置顺序不是非递减的；
• 在调用 placeCard 之后仍继续调用 grader 函数；
• playGame 在未调用 placeCard 的情况下结束。

对于采用 Binary 评分的子任务，只要不违规并且成功完成游戏，即获得该子任务满分。

对于采用 Partial 评分的子任务，若不违规，则会根据所需轮数获得部分分。原题面使用表格给出各子任务的评分类型，详见下方子任务表。

---

子任务

子任务	分值	$N$	$M$	$H$	$R_{\max}$	评分方式	额外限制
1	9	$\le 60$	$=100$	$=6$	$1500$	Binary	无
2	10	$\le 30$	$=6$		$1800$		所有抽到的值互不相同
3	11						无
4	12	$\le 60$			$1500$	Partial	至少有一位玩家抽到 $0$
5	13						所有抽到的值互不相同
6	16						无
7	29		$=2$

---

本地测试（单进程）

题目提供本地 grader：Lgrader.cpp。它可以用来测试：

• 生成提示 giveHint；
• 从某个玩家视角模拟 playGame。

测试 giveHint

输入格式：

• 0
• N M H
• $C_0\ C_1\ \dots\ C_{N-1}$

其中 $C_i$ 表示第 i 位玩家抽到的卡牌值。

grader 会输出你生成的提示。

测试某位玩家的 playGame

输入格式：

• 1
• N M H
• $C_0\ C_1\ \dots\ C_{N-1}$
• i h
• L
• $P_0\ P_1\ \dots\ P_{L-1}$

其中：

• i：要模拟的玩家编号；
• h：提示值；
• L：在该玩家第一轮行动前，已经放下卡牌的玩家数；
• P：这些玩家的编号列表。

在本地模拟中：

• 若玩家选择 passTurn()，grader 会输出 0；
• 若玩家选择 placeCard()，grader 会输出 1 并结束。

每次 grader 输出 0 后，还会再读入：

• K
• $Q_0\ Q_1\ \dots\ Q_{K-1}$

其中 K 表示在这一轮到下一次该玩家行动之间，有多少位玩家放下了卡牌，$Q$ 为这些玩家的编号列表。

---

本地测试（完整游戏）

题目还提供了程序 Lmanager.py，用于在本地模拟整场游戏。

你应先将自己的程序与 Lgrader.cpp 一起编译成可执行文件，然后运行：

python Lmanager.py <你的可执行文件路径>

输入格式为：

• N M H Rmax
• $C_0\ C_1\ \dots\ C_{N-1}$

管理器会启动 $N+1$ 个进程来模拟整局游戏。

---

示例交互

设：

• $N = 4$
• $M = 5$
• $H = 6$

且玩家抽到的卡牌分别为：

4 0 0 3

将各进程分别称为“Klimi”、“玩家 0”、“玩家 1”、“玩家 2”、“玩家 3”。

则一组可能的交互过程如下：

1. Klimi：调用 giveHint(4, 5, 6, {4, 0, 0, 3})
2. Klimi：giveHint 返回 1
3. 玩家 0：调用 playGame(4, 5, 6, 0, {-1, 0, 0, 3}, 1, {})
4. 玩家 0：调用 passTurn()
5. 玩家 1：调用 playGame(4, 5, 6, 1, {4, -1, 0, 3}, 1, {})
6. 玩家 1：调用 placeCard() 并结束执行
7. 玩家 2：调用 playGame(4, 5, 6, 2, {4, 0, -1, 3}, 1, {1})
8. 玩家 2：调用 passTurn()
9. 玩家 3：调用 playGame(4, 5, 6, 3, {4, 0, 0, -1}, 1, {1})
10. 玩家 3：调用 passTurn()
11. 玩家 0：passTurn() 返回 {1}
12. 玩家 0：再次调用 passTurn()
13. 玩家 2：passTurn() 返回 {}
14. 玩家 2：调用 placeCard() 并结束执行
15. 玩家 3：passTurn() 返回 {2}
16. 玩家 3：调用 placeCard() 并结束执行
17. 玩家 0：passTurn() 返回 {2, 3}
18. 玩家 0：调用 placeCard() 并结束执行

最终整局游戏在 3 轮 内成功完成。