QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Communication

#6985. 纸牌魔术

Statistics

两名玩家将使用一副标准的 52 张牌进行纸牌魔术表演。为方便起见,牌的数值为 0 到 51 之间的不同整数。

牌最初以某种玩家未知的顺序正面朝上(数值可见)放置在桌子的一行中。

第一名玩家走到桌子旁,查看这些牌,并进行最多 $S$ 次交换。每次交换通过选择位置 $i$ 和 $j$ 上的两张牌($i$ 和 $j$ 可以相等)并将位置 $i$ 的牌移动到位置 $j$,反之亦然来完成。

之后,第一名玩家在不与第二名玩家交流的情况下离开,所有牌在不改变顺序的情况下被翻转(其数值不再可见)。第二名玩家被邀请到桌子旁,被要求猜出数值为 target 的牌在哪里,并允许逐个翻开最多 $T$ 张牌。如果翻开的任何一张牌是 target,则玩家获胜。如果他们的猜测次数用尽,则他们失败。

你的目标是编写两个程序,模拟玩家的行为并赢得游戏。

实现细节

你将获得两个程序——FirstPlayerSecondPlayer,以及一个样例评测程序。

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$

子任务

  1. (16 分):$S = 52, T = 1$
  2. (20 分):$S + T = 52$
  3. (22 分):$S = 13, T = 27$
  4. (18 分):$S = 1, T = 26$
  5. (24 分):对于给定的 $S$ 和 $T$ 存在获胜策略

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.