#P826. Risk的胜率

    ID: 826 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 2 上传者: 标签>搜索记忆化搜索记忆化搜索DD模拟赛之处女座

Risk的胜率

问题描述

Risk是经典的策略战棋类游戏,曾多次作为NOI团体赛的比赛项目。在用人工智能的方法决定最优的游戏策略时,用概率来计算策略的可行性是基本不可避免的课题。这里需要计算的,是Risk游戏中发起单次战斗的胜利概率。

战斗是Risk游戏中的核心单元。一次战斗,指一个玩家使用己方国家上的部队攻击某个相邻国家的敌方部队。设攻击方有N支部队,防守方有M支部队。

战斗过程分为若干轮进行。每轮攻击,攻击方可以从N支部队中选择K支部队出战,这里K只可以取1,2或3。同时,必须满足K<=N-1,也就是说,攻击方在出战的同时,必须在自己的国土上留下至少1支部队。在这里,我们假定,攻击方总会选择尽可能多的部队出战。作为防守方,如果他的部队数不小于2,就会派出2支部队进行防御,否则只能派仅有的1支部队进行防御。

攻击方出战的每支部队以及防守者进行防御的每支部队会投一颗点数为1~6的均匀的骰子,得到的值表示这支部队当前的战斗力。战斗力计算完毕后,攻击方战斗力最高的部队将对战防守方战斗力最高的部队,攻击方战斗力第二高的部队对战防守方战斗力第二高的部队(如果二者都存在的话),攻击方战斗力最低的一支部队不参与此轮对战。

两支部队对战的结果是某支部队会被消灭。事实上,如果防守方部队的战斗力不小于攻击方部队的战斗力,攻击方的这支部队会被消灭。仅当攻击方部队的战斗力大于防守方部队的战斗力时,被消灭的是防守方部队。

若某轮攻击过后,防守方的部队数减为0,则攻击方成功地占领了防守方的国家,胜者是攻击方;如果攻击方的部队数减为1,则它再也无法派出部队进行攻击,我们称此时的胜者是防守方。

在上述定义下,可以看出,每次攻击的胜者完全取决于骰子的点数。

现在,dd_engi想知道,如果他的国家有N支军队,作为攻击方,面对敌国的M支部队,在骰子均匀的前提下,获胜的概率是多少呢?

输入格式

每个输入文件包含多组数据,每个数据一行。

每行包括用空格隔开的两个整数N与M。

输出格式

对于每个输入数据,输出一行一个数,即dd_engi的获胜概率。保留两位小数,四舍五入。

样例输入

2 1

5 5

样例输出

0.42

0.36

数据范围

2 <= N <= 30; 1 <= M <=30。