logo AlgoBeat OnlineJudge
登录 注册

#101867. [BZOJ 1867] [Noi1999]钉子和小球

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一个三角形木板,竖直立放,上面钉着 颗钉子,还有 个格子 (当 时如图 1 )。每颗钉子和周围的钉子的距离都等于 ,每个格子的宽度也都等于 ,且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。

让一个直径略小于 的小球中心正对着最上面的钉子在板上自由滚落,小球每碰到一个钉子都可能落向左边或右边 (概率各 )我们知道小球落在第 个格子中的概率 ,其中 为格子的编号,从左至右依次为

现在的问题是计算拔掉某些钉子后,小球落在编号为 的格子中的概率 。假定最下面一排钉子不会被拔掉。例如图 是某些钉子被拔掉后小球一条可能的路径。

a

上面三个图分别为图

输入格式

第一行为整数

以下 行依次为木板上从上至下 行钉子的信息,每行中*表示钉子还在,.表示钉子被拔去,注意在这 行中空格符可能出现在任何位置。

输出格式

仅一行,是一个既约分数( 写成 ),为小球落在编号为 的格子中的概率

既约分数的定义: 是既约分数,当且仅当 为正整数且 没有大于 的公因子。

样例

样例

样例输入 #1

5 2
    *  
   * .
  * * *
 * . * *
* * * * *

样例输出 #1

7/16

数据范围与提示

对于所有数据,