#1470. 「THUPC 2021 初赛」狗蛋和二五仔

「THUPC 2021 初赛」狗蛋和二五仔

题目背景

那女孩对我说
代价为十辆铲车

题目描述

小 E 喜欢和老师变换着花样玩牌。最近,他们又发明了一种叫做“狗蛋和二五仔”的玩法。

规则是这样的:

游戏开始时小 E 和老师各有 3030 点体力值,手上各有 22 张牌。所有的牌是完全相同的。每个玩家的面前都可以放置牌,开始时双方面前没有任何牌。

双方轮流进行操作。玩家在每个自己的回合开始时先抽一张牌。“抽一张牌”的操作指的是,如果手上的牌的数量小于 33 张,则再抓一张牌放在手上;如果手上恰好有 33 张牌,则不能再抓牌。操作分为 44 种类型。

  • 技能。让自己的体力值 2- 2,然后抽一张牌。

  • 攻击。具体地,玩家可以选择一张放在自己面前的本回合还未攻击过的牌,选择对方面前的一张牌同归于尽,或者选择一张放在自己面前的本回合还未攻击过的牌,让对方的体力值 3- 3。如果是后者,则将这张选择的牌标记为已攻击。

  • 打牌。如果你面前的牌的数量小于 44 张,且手上有牌才能进行此操作。先进行下面的过程 33 次:

    • 随机选择一个角色,让它的体力值 1- 1。这个角色可以是自己、对方或者某一方面前的一张牌。如果双方场上的牌一共有 kk 张,那么选择到任何一个角色的概率为 1k+2\frac{1}{k + 2}。如果该角色是一张牌且体力值变为了 00,那么将它摧毁;如果该角色是一个玩家且体力值变为了 00,那么该玩家直接输掉游戏。

    在进行完 33 次后将手上的一张牌放在自己面前。牌的体力值为 22。这张牌在本回合中被认为已攻击过。

  • 结束回合,接下来轮到对方的回合。

一回合中,玩家可以进行多次操作,但是技能和打牌的操作次数之和不能超过 OO。除了结束回合,这些操作没有顺序限制,比如你可以先打一张牌,然后使用技能,然后再打一张牌。在结束回合之前,玩家需要进行至少一次任意的操作才能结束回合。

在任何时刻如果有玩家的体力值小于或等于 00,那么该玩家输掉游戏。

游戏进行了几个回合后,现在轮到了小 E 的回合开始前。小 E 想让你帮他分析,如果双方都采用最优策略,那么现在自己赢的概率是多少。

输入格式

第一行一个正整数 T,OT, O,分别表示数据组数和每回合中技能和打牌的操作次数上限。
对于每组数据,第一行两个正整数 E,SE, S,分别表示小 E 和老师现在的体力值。保证 1E,S201 \le E, S \le 20
第二行一个非负整数 cc,然后跟着 cc 个正整数 a1,,aca_1, \ldots , a_c,表示老师面前有 cc 张牌,它们的体力值分别为 a1,,aca_1, \ldots , a_c。保证 0c40 \le c \le 41ai21 \le a_i \le 2
第三行一个非负整数 pp,然后跟着 pp 个正整数 e1,,epe_1, \ldots , e_p,表示小 E 面前有 pp 张牌, 它们的体力值分别为 e1,,epe_1, \ldots , e_p。保证 0p40 \le p \le 41ei21 \le e_i \le 2
第四行两个 [0,3][0, 3] 之间的非负整数,分别表示老师和小 E 的手牌数。
在你到来之前老师可能作了弊,你不需要判断输入的情况是否真的是游戏进行了几个回合后的情况。

输出格式

对于每组数据输出一行一个实数,表示小 E 在双方采用最优决策时获胜的概率。你的输出的和标准答案的绝对误差不超过 106{10}^{-6} 时算作正确。

样例

1 5
1 1
0
0
0 1

0.500000000

回合开始,小 E 抽一张牌。此时小 E 手上有 22 张牌,老师手上没有牌,双方的面前都没有牌。双方的体力值均为 11。这时,最优策略下,小 E 不能使用技能,因为使用后会因为自己的体力值小于等于 00 而输掉游戏;小 E 不能攻击,因为自己面前没有牌;小 E 也不能结束回合,因为本回合他还没有进行任何操作。所以小 E 的最优策略是打一张牌,这时会随机选到小 E 或者老师中的一个角色,让他体力值 1- 1 然后输掉游戏。所以小 E 的获胜概率为 0.50.5

数据范围与提示

保证 1T3514931 \le T \le 3514933O53 \le O \le 5

后记

最后小 E 还是战胜了老师。

“老师你术士玩多了就知道怎么玩了,你打得还不够多。”

“吹牛现在都流行这么吹的吗?兄弟你知道我术士多少胜场嘛,啊?我跟你说全世界没有一个人术士比我胜场多的。”

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。