← 返回题目列表

AtCoder · arc055_b

B. 米果

中文机器翻译题面 查看原题

問題文

在CoDeer,鹿喜欢米果。现在,AtCoDeer君是 编号为1~N编号的N我把目光投向了传闻中给我饼干的高桥君。数字越大,价值越高,所以AtCoDeer就是数字 我绝对想尝尝N的米果。不过,因为AtCoDeer的肚子已经饱了,K您最多只能吃一块米果。

高桥君提前对N个仙贝进行了分类,一一我会尝试依次把米果给AtCoDeer。 AtCo鹿君i(1≦i≦N)当你收到第一块饼干时,你必须决定是否要吃它。那时选择。但已经 如果你已经吃过K,你就不能再吃了。如果你不吃的话,高桥君就会吃掉它,所以AtCoDeer君以后就吃不到了。AtCoDeer 无法说出看到米果的数量,但他可以比较他见过的所有米果(包括他吃过的米果)的大小。

高桥君给饼干的顺序是随机的(N!等概率排列),而 AtCoDeer 事先并不知道这一点。 当AtCoDeer采用最优策略时,他最终达到了 求 AtCoDeer 能吃掉N米果的概率。

制約

  • 1≦K≦N≦1000

入力

输入将以以下格式从标准输入提供。

N K

出力

当AtCoDeer君采取最优策略时,他终于得到了米果。 打印吃东西的概率N。输出有绝对或相对误差。10^{-6}以内,则允许。


入力例1

3 1

出力例1

0.500000000000

以下策略是最好的:

  • 我不会吃第一个。
  • 如果第二块比第一块大,就吃掉它。
  • 如果你还能吃第三个(如果你还没有吃过第二个),那就吃吧。
此时,如果观看米果的顺序是1、3、2、2、1、3、2、3、1,那么你可以吃到3个米果,所以概率是3/3! = 1/2。


入力例2

17 17

出力例2

1.000000000000

由于有可能吃掉所有米果,因此所需的概率为 1。


入力例3

1000 10

出力例3

0.984898795563