#P3095. Linear Pachinko
Linear Pachinko
问题描述
这个问题灵感来自日本流行的游戏柏青哥()。传统的柏青哥机器是垂直弹球机和老虎机的结合体。玩家用弹射器将小钢球发射到机器的顶部,类似于弹球游戏。球在掉落过程中会经过一系列钉子,这些钉子会改变球的路径。最终,球要么从底部的洞中掉出并消失,要么落在机器中的某个奖励门中,玩家会获得不同数量的球。如果玩家收集到足够多的球,就可以兑换奖品。
对于这个问题,我们考虑一种线性柏青哥机器,它由以下一种或多种字符组成:洞(),地板( _ ),墙(|),山(/\)。注意:墙或山永远不会相邻。玩家随机在机器的某个字符上方投下一个球,所有起始位置的概率均等。球的运动规则:如果球掉入洞(),则直接掉落通过。如果球掉在地板(_)上,则立即停止。如果球掉在山的左侧(),则向左滚动,经过任意数量的连续地板,直到:掉入一个洞,从机器左端掉落,碰到墙或山而停止。如果球掉在山的右侧(\),则行为类似,但方向向右。如果球掉在墙(|)上,则行为类似于山的左侧或右侧,每种情况的概率为 。计算球随机投下时,最终掉入洞或从机器两端掉落的概率(以百分比表示,截断小数部分)。
比如,考虑以下机器(字符位置编号仅用于说明,不属于机器本身):
123456789
/\.|__/\.
各位置的掉落概率如下:位置 ():(向左滚动并从左端掉落),位置 (\):(向右滚动并掉入位置 的洞),位置 ():(直接掉落),位置 ():(可能向左或向右,但无论哪种方式都会碰到墙或山而停止),位置 ( _ ):(停止在地板上),位置 (_):(同上),位置 ():(向左滚动并掉入位置 的洞),位置 ():(直接掉落),位置 ():(直接掉落)。
整体概率为这些值的平均值:
$$\frac{100 + 100 + 100 + 50 + 0 + 0 + 100 + 100 + 100}{9} \approx 61.111\% $$输入格式
输入包含一个或多个线性柏青哥机器,每行一个,长度为 到 个字符。输入以单独一行 # 结束。
输出格式
对每个机器,计算掉落概率的百分比(截断小数部分),每行输出一个整数。
输入样例
/\.|__/\.
_._/\_|.__/\./\_
...
___
./\.
_/\_
_|.|_|.|_|.|_
____|_____
#
输出样例
61
53
100
0
100
50
53
10
来源
2006年美国中北部地区