#YDRG005F. Z 老师的天才 Mahjong 挑战赛!

Z 老师的天才 Mahjong 挑战赛!

[UPD 1] 下发文件请加群 794212373,下载 F.zip 后使用密码 ur1vthFUIEG2852SGHWGdbba3w25 解压。

灵感来源:《天胡街浪子》中,原田和天的最终战。>

出这道题的一个原因是为了图一乐,还有一个原因是敝人希望看到更多 creative 的做法,因为这道题在内测的时 候没有多少人开(

不是很敢保证这道题的区分度,但是这道题花费了我很多精力,希望大家喜欢,祝大家玩得开心喵~

Total Score: 100100.

题目描述

请不要卡评测。

这是一道交互题。(标题下方的传统题标签请忽略。)

本题所使用麻将规则可能和现实中有所不同,即使你很熟悉麻将,也请认真阅读下述规则。

本题中所使用的麻将,由 33 种花色(万筒条),每种花色 99 种点数(1,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,9),每种点数 44 张牌,一共 3×9×4=1083 \times 9 \times 4=108 张牌组成。我们用 m 表示万,p 表示筒,s 表示条,例如“一万”表示为 1m,“五条”表示为 5s

一个面子指三张花色相同,且点数相同或连续的牌,例如 1m 1m 1m3s 4s 5s。一个雀头指两张花色相同且点数相同的牌,例如 2p 2p9s 9s

一种 1414 张牌的组合被称为胡的当且仅当存在一种方案可以将其分成四个面子和一个雀头(每一张牌仅属于一个面子或雀头)。本题中考虑国士无双、七对等非常规胡法。例如 1m 2m 3m 4m 5m 6m 2p 2p 2p 8s 8s 8s 9s 9s 是胡的。

某张牌属于一种 1313 张牌的组合的听牌集合,当且仅当这 1313 张牌加上这张新牌构成的 1414 张牌是胡的,且1414 张牌不存在任意一种牌出现 5\ge 5 次,例如 1m 1m 1m 2m 2m 2m 3m 3m 3m 5p 5p 5p 5p 的听牌集合为空,因为加入 5p 后会出现 555p1m 1m 1m 2m 2m 2m 3m 3m 3m 4m 4m 2s 3s 的听牌集合是 {\{1s,,4s}\}1m 1m 1m 2m 2m 2m 3m 3m 3m 2s 2s 3s 3s 的听牌集合是 {\{2s,,3s}\}

在本题中,你需要和交互库玩如下游戏:

  1. 游戏开始时,交互库将这一副麻将按某种顺序排列组成牌堆,保证牌堆顶 1313 张牌的听牌集合大小 2\ge 2
  2. 交互库将牌堆顶 1313 张牌作为她的手牌,然后将牌堆顶第 1414 张到第 4343 张牌(共 3030 张牌)亮出,你可以看到这些牌,注意这些牌可能属于交互库手牌的听牌集合,也可能不属于。然后移除这 4343 张牌(即此时牌堆顶的牌,是初始牌堆的牌堆顶第 4444 张牌)。
  3. 你猜测一张牌,若这张牌属于交互库手牌的听牌集合,则游戏结束;否则交互库会亮出牌堆顶的 33 张牌中不属于听牌集合的所有牌,并移除牌堆顶的 33 张牌,你需要继续猜测。注意,如果听牌集合内的一张牌全部被翻出,其仍然属于听牌集合
  4. 游戏结束时,令你的代价为你的猜测次数。

你需要尽可能最小化游戏的代价。

请认真阅读“数据生成方式”和“评分方式”

实现细节与交互方式

你的程序名必须为 mahjong.cpp,且必须包含头文件 mahjong.h。你不需要,也不应该实现主函数。你禁止读入或输出任何内容。你只需要实现 init()play_game() 函数。

void init(int T);

此函数仅在交互开始时调用一遍,其中 TT 表示游戏局数。

void play_game(vector <string> vec);

此函数会被调用 TT 次,其中 vec 的长度为 3030,表示亮出的 3030 张牌(原牌堆顶第 14144343 张牌)。

你可以在 play_game() 函数中调用如下函数:

vector <string> guess(string str);

这个函数表示一次猜测,其中 str 表示你猜测的牌,返回值有两种情况:

  1. 返回一个长度为 33 的 vector,每一项要么表示一张不属于听牌集合的牌,要么用 "-1" 表示一张属于听牌集合的牌。如果这张牌不存在(牌堆没牌了),则也会用 "-1" 代替
  2. 返回一个长度为 11 的 vector,其中仅包含一项,内容为 "CORRECT",表示你猜中了,游戏结束。当收到这个结果后你应该立即结束 play_game() 函数,否则可能发生不可预料的后果

你可以查看下发文件中的 mahjong_sample.cpp,这是一个实现的例子,只保证它能通过题面中的样例

你可以查看下发文件中的 grader.cpp,这是一个样例交互库,它和最终测试所用交互库有着相同的功能和相似的实现方式

如何测试你的程序

编译命令:g++ -std=c++14 -O2 -o grader grader.cpp mahjong.cpp。编译完成后,你得到可执行文件 grader

你可以按如下格式往标准输入中输入,你也可以利用 freopen 等语句将输入进行重定向:

T
card1_1 card1_2 card1_3 ... card1_108
card2_1 card2_2 card2_3 ... card2_108
...
cardT_1 cardT_2 cardT_3 ... cardT_108

其中 cardx_i 表示第 xx 局游戏的牌堆顶第 ii 张牌。你需要保证牌的表示正确,且前 1313 张牌的听牌集合大小 2\ge 2,否则可能会发生无法预料的后果

交互库会向标准输出中输出,你也可以利用 freopen 等语句将输出进行重定向:

  • Invalid input [0] T>104T \gt 10^4
  • Invalid input [1]:字符串数量不正确。
  • Invalid input [2]:存在一个字符串,表示的不是一张合法的麻将牌。
  • Invalid input [3]:存在一局游戏,牌堆中有一张麻将牌出现 >4\gt 4 次。
  • Invalid input [4]:前 1313 张牌听牌集合大小 <2\lt 2
  • Wrong Answer [0]:你调用了太多的 guess() 函数(>270000\gt 270000 次)。
  • Wrong Answer [1]:你在 guess() 函数中,传入的参数表示的不是一张正确的麻将牌。
  • Accepted! Cost = cost. Score = score. ,其中 costcost 为你 TT 局游戏代价的总和,scorescore 为你的得分。

注意:

  • 交互库不会对你的输入数据生成方式进行任何的检验,即不会因你的输入不符合下文的“数据生成方式”而报错
  • 若不按上文中“实现细节与交互方式”部分所述方式交互,可能发生无法预料的后果

样例

操作 解释
init(1); 被交互库调用。 表示游戏局数为 11
play_game(thirty_cards); 被交互库调用。 表示第一局游戏,并给定 3030 张牌。
guess("3m"); 被选手在 play_game() 中调用。 表示一次猜测,猜测的牌为 3m
{"8p","-1","9p"} 被返回。 牌堆顶的三张牌,第一三张为 8p 9p,第二张因为在听牌集合内被 -1 代替。
guess("3s"); 被选手在 play_game() 中调用。 表示一次猜测,猜测的牌为 3s
{"3s","4s","5s"} 被返回。 牌堆顶的三张牌分别为 3s 4s 5s
guess("4p");被选手在 play_game() 中调用。 表示一次猜测,猜测的牌为 4p
{"CORRECT"} 被返回。 猜测正确,游戏结束,代价为 33,此时 play_game() 应该立即结束。
  • thirty_cards={"1m","1m","1m","1m","2m","2m","2m","2m","3m","3m","3m","3m","4m","4m","4m","4m","5m","5m","5m","5m","6m","6m","6m","6m","7m","7m","7m","7m","8m","8m"}

  • 交互库的手牌为:{"1s","1s","1s","2s","2s","2s","3s","3s","3s","4s","4s","5p","6p"}

  • 牌堆从第 4444 张牌开始依次为:{"8p","7p","9p","3s","4s","5s",...}

    此样例的完整版可以在下发文件中的 mahjong_small.in 中找到

数据生成方式

在最终测试中,T=104T=10^4

生成数据时,两张同花色同点数的牌可区分,即看做不同的牌。

每一局游戏的牌堆均在所有前 1313 张牌听牌集合**大小 2\ge 2 **的 108108 张牌的排列中,等概率随机选择一个。交互过程中牌堆不会动态变化。

你可查看选手目录下的 mahjong.in,这是一个按如上方式生成的数据。

此数据和最终测试数据不完全相同,但均使用上述方式生成。

评分方式

若交互过程顺利结束,则根据你的 TT 局游戏的代价之和 costcost 得到分数,否则得到 00 分。

costcost 和得分满足如下关系,本题的满分为 100100

costcost 得分
cost<45000cost \lt 45000 $\min\{100,5.41\times 10^{-6}\cdot(cost-45000)^2+26\}$
45000cost<5000045000 \le cost \lt 50000 20+650000cost500020+6\cdot \frac {50000-cost}{5000}
50000cost<14000050000 \le cost \lt 140000 2020
140000cost270000140000 \le cost \le 270000 55
>270000\gt 270000 00

再次强调:本题只有一个测试点,任何超出时间限制(TLE)、超出空间限制(MLE)、运行错误(RE)、交互格式不正确等错误,均可能导致你得到 00

交互库会占用不超过 1s1\text{s} 的时间和 128MB128\text{MB} 的空间,此项时空消耗均被计算在本题时空限制内,请确保你的程序为此项消耗留出了足够的时间和空间。

显然,得到此题的满分的次数限制(4130141301 次)并不是次数的下界,欢迎各路神仙吊打 std!