题目背景

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

题目描述

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

规则是这样的：

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

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

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

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

• 打牌。如果你面前的牌的数量小于 $4$ 张，且手上有牌才能进行此操作。先进行下面的过程 $3$ 次：

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

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

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

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

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

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

输入格式

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

输出格式

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

样例

1 5
1 1
0
0
0 1

0.500000000

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

数据范围与提示

保证 $1 \le T \le 351493$，$3 \le O \le 5$。

后记

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

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

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

来源

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

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