#P1644. 赌还是不赌 ID: 645 远端评测题 1000ms 10MiB Hydro 标签>

描述

亚历山大·查尔斯·麦克米伦热衷于赌博，在上次去赌场时，他碰到了一款新游戏。该游戏在如下所示的一排方格上进行。

起初，一枚筹码被放置在“起始”方格处。玩家要通过一系列回合将筹码移动到“结束”方格，游戏至此结束。每回合都会抛一枚硬币：若硬币正面朝上，筹码向右移动一格；若硬币反面朝上，筹码向右移动两格（若筹码距离“结束”方格仅一格之遥，那它就直接移至“结束”方格）。之后，必须遵循筹码所落方格上的指示。每个指示属于以下类别之一：

1. 向右移动 $n$ 格（$n$ 为正整数）
2. 向左移动 $n$ 格（$n$ 为正整数）
3. 跳过一回合
4. 无指示

遵循指示后，该回合结束，新的回合开启。需注意，筹码仅在抛硬币后遵循其所落方格上的指示。例如，若筹码落在一个指示其向左移动 3 格的方格上，就进行移动，但移动后所在方格的指示会被忽略，回合结束。此游戏的赌博规则如下：给定一个棋盘布局和一个整数 $T$，你要下注猜测游戏是否会在 $T$ 回合内结束。

亚历山大输得身无分文，连好几件衣服都搭进去了，他决定寻求专业帮助——并非为戒掉赌瘾，而是编写一个程序来帮他决定在此游戏中如何下注。

输入

输入包含多个测试用例。首行包含一个整数 $n$，表示测试用例的数量。每个测试用例包含两行：第一行包含两个整数 $m$ 和 $T$（$1 \leq m \leq 50$，$1 \leq T \leq 40$），其中 $m$ 是除“起始”和“结束”方格外棋盘的方格数，$T$ 是目标回合数。第二行包含棋盘上 $m$ 个内部方格的指示。方格的指示以单个空格分隔，方格指示为以下形式之一：$+n$、$-n$、$L$ 或 $0$（数字零）。$+n$ 表示向右移动 $n$ 格，$-n$ 表示向左移动 $n$ 格，$L$ 表示跳过一回合，$0$ 表示该方格无指示。任何向右或向左的移动都不会让你移出棋盘。

输出

每个测试用例的输出为一行，可能是：

• “Bet for. x.xxxx”，如果你认为游戏在 $T$ 回合或更少回合内结束的概率超过 50%；
• “Bet against. x.xxxx”，如果你认为游戏在 $T$ 回合或更少回合内结束的概率低于 50%；
• “Push. 0.5000”，其他情况。 其中，$x.xxxx$ 是游戏在 $T$ 回合或更少回合内结束的概率，四舍五入保留四位小数。（注意，由于输出时对计算出的概率进行了四舍五入，“Bet for.” 或 “Bet against.” 消息后可能会出现概率为 0.5000 的情况。）

输入数据 1

5
4 4
0 0 0 0
3 3
0 -1 L
3 4
0 -1 L
3 5
0 -1 L
10 20
+1 0 0 -1 L L 0 +3 -7 0

输出数据 1

Bet for. 0.9375
Bet against. 0.0000
Push. 0.5000
Bet for. 0.7500
Bet for. 0.8954

来源

2000 年北美中东部地区赛