#P52068. 「THUPC 2021 初赛」狗蛋和二五仔
「THUPC 2021 初赛」狗蛋和二五仔
题目背景
那女孩对我说
代价为十辆铲车
题目描述
小 E 喜欢和老师变换着花样玩牌。最近,他们又发明了一种叫做“狗蛋和二五仔”的玩法。
规则是这样的:
游戏开始时小 E 和老师各有 点体力值,手上各有 张牌。所有的牌是完全相同的。每个玩家的面前都可以放置牌,开始时双方面前没有任何牌。
双方轮流进行操作。玩家在每个自己的回合开始时先抽一张牌。“抽一张牌”的操作指的是,如果手上的牌的数量小于 张,则再抓一张牌放在手上;如果手上恰好有 张牌,则不能再抓牌。操作分为 种类型。
-
技能。让自己的体力值 ,然后抽一张牌。
-
攻击。具体地,玩家可以选择一张放在自己面前的本回合还未攻击过的牌,选择对方面前的一张牌同归于尽,或者选择一张放在自己面前的本回合还未攻击过的牌,让对方的体力值 。如果是后者,则将这张选择的牌标记为已攻击。
-
打牌。如果你面前的牌的数量小于 张,且手上有牌才能进行此操作。先进行下面的过程 次:
- 随机选择一个角色,让它的体力值 。这个角色可以是自己、对方或者某一方面前的一张牌。如果双方场上的牌一共有 张,那么选择到任何一个角色的概率为 。如果该角色是一张牌且体力值变为了 ,那么将它摧毁;如果该角色是一个玩家且体力值变为了 ,那么该玩家直接输掉游戏。
在进行完 次后将手上的一张牌放在自己面前。牌的体力值为 。这张牌在本回合中被认为已攻击过。
-
结束回合,接下来轮到对方的回合。
一回合中,玩家可以进行多次操作,但是技能和打牌的操作次数之和不能超过 。除了结束回合,这些操作没有顺序限制,比如你可以先打一张牌,然后使用技能,然后再打一张牌。在结束回合之前,玩家需要进行至少一次任意的操作才能结束回合。
在任何时刻如果有玩家的体力值小于或等于 ,那么该玩家输掉游戏。
游戏进行了几个回合后,现在轮到了小 E 的回合开始前。小 E 想让你帮他分析,如果双方都采用最优策略,那么现在自己赢的概率是多少。
输入格式
第一行一个正整数 ,分别表示数据组数和每回合中技能和打牌的操作次数上限。
对于每组数据,第一行两个正整数 ,分别表示小 E 和老师现在的体力值。保证 。
第二行一个非负整数 ,然后跟着 个正整数 ,表示老师面前有 张牌,它们的体力值分别为 。保证 ,。
第三行一个非负整数 ,然后跟着 个正整数 ,表示小 E 面前有 张牌,
它们的体力值分别为 。保证 ,。
第四行两个 之间的非负整数,分别表示老师和小 E 的手牌数。
在你到来之前老师可能作了弊,你不需要判断输入的情况是否真的是游戏进行了几个回合后的情况。
输出格式
对于每组数据输出一行一个实数,表示小 E 在双方采用最优决策时获胜的概率。你的输出的和标准答案的绝对误差不超过 时算作正确。
样例
1 5
1 1
0
0
0 1
0.500000000
回合开始,小 E 抽一张牌。此时小 E 手上有 张牌,老师手上没有牌,双方的面前都没有牌。双方的体力值均为 。这时,最优策略下,小 E 不能使用技能,因为使用后会因为自己的体力值小于等于 而输掉游戏;小 E 不能攻击,因为自己面前没有牌;小 E 也不能结束回合,因为本回合他还没有进行任何操作。所以小 E 的最优策略是打一张牌,这时会随机选到小 E 或者老师中的一个角色,让他体力值 然后输掉游戏。所以小 E 的获胜概率为 。
数据范围与提示
保证 ,。
后记
最后小 E 还是战胜了老师。
“老师你术士玩多了就知道怎么玩了,你打得还不够多。”
“吹牛现在都流行这么吹的吗?兄弟你知道我术士多少胜场嘛,啊?我跟你说全世界没有一个人术士比我胜场多的。”
来源
来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。
题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。