两名玩家将使用一副标准的 52 张牌进行纸牌魔术表演。为方便起见,牌的数值为 0 到 51 之间的不同整数。
牌最初以某种玩家未知的顺序正面朝上(数值可见)放置在桌子的一行中。
第一名玩家走到桌子旁,查看这些牌,并进行最多 $S$ 次交换。每次交换通过选择位置 $i$ 和 $j$ 上的两张牌($i$ 和 $j$ 可以相等)并将位置 $i$ 的牌移动到位置 $j$,反之亦然来完成。
之后,第一名玩家在不与第二名玩家交流的情况下离开,所有牌在不改变顺序的情况下被翻转(其数值不再可见)。第二名玩家被邀请到桌子旁,被要求猜出数值为 target 的牌在哪里,并允许逐个翻开最多 $T$ 张牌。如果翻开的任何一张牌是 target,则玩家获胜。如果他们的猜测次数用尽,则他们失败。
你的目标是编写两个程序,模拟玩家的行为并赢得游戏。
实现细节
你将获得两个程序——FirstPlayer 和 SecondPlayer,以及一个样例评测程序。
在 FirstPlayer 中,你必须实现以下函数:
void swapCards(int cards[], int S, int T)
- 该函数由评测程序恰好调用一次。
cards:一个包含从左到右初始牌值的数组,共有 52 个元素,索引从 0 到 51。S:允许的交换次数。T:允许的猜测次数。
swapCards 可以调用以下函数:
void doSwap(int i, int j)
i:要交换的第一张牌的索引,$0 \le i < 52$。j:要交换的第二张牌的索引,$0 \le j < 52$。doSwap最多可以被调用 $S$ 次。
在 SecondPlayer 中,你必须实现以下函数:
void guessCard(int S, int T, int target)
S:允许的交换次数。T:允许的猜测次数。target:应该被揭示的牌的数值。
guessCard 可以调用以下函数:
int guess(int idx)
idx:猜测的索引,$0 \le idx < 52$。- 它返回第
idx张牌的数值。 guess最多可以被调用 $T$ 次。- 当猜中正确牌时,评估成功终止。
样例
以下是附加评测程序的输入示例。
第一行应包含两个整数:$S$ 和 $T$。
第二行应包含 52 个数字。第 $i$ 个数字表示第 $i$ 张牌的数值。
第三行包含一个整数 target。
| 样例输入 | 样例调用 |
|---|---|
| 1 51 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 1 |
swapCards([0,1,…], 1, 51) |
doSwap(0, 1) |
|
swapCards 结束 |
|
guessCard(1, 51, 1) |
|
guess(5) |
|
guess(1) |
|
guess(0) |
说明
样例调用说明:
doSwap(0, 1):交换索引为 0 和 1 的牌。
guess(5):guess 返回 5。
guess(1):guess 返回 0。
guess(0):正确!
数据范围
- $1 \le S \le 52$
- $1 \le T \le 51$
- $0 \le target < 52$
子任务
- (16 分):$S = 52, T = 1$
- (20 分):$S + T = 52$
- (22 分):$S = 13, T = 27$
- (18 分):$S = 1, T = 26$
- (24 分):对于给定的 $S$ 和 $T$ 存在获胜策略