← 返回题目列表

Codeforces · 464/D

D. 暗筏世界 - 2

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

Roma在游戏“World of Darkraft - 2”中发现了一个新角色。在这个游戏中,角色与怪物战斗,找到越来越先进的东西,让他与更强大的怪物战斗。

角色可以为自己装备k种不同类型的物品。每个项目的力量取决于其级别(正整数)。最初,角色拥有 k 种类型中每一种的 1 级物品。

战胜怪物后,角色恰好找到了一件新的随机生成的物品。生成过程如下所示。首先定义item的类型; k 种类型中的每一种都有相同的概率。然后定义新项目的级别。假设此时玩家所选类型的物品等级等于 t。新项目的级别将在段 [1; 的整数中统一选择。 t + 1]。

从新物品和当前玩家相同类型的物品中,罗马选择最好的一件(即等级更高的一件)并装备它(如果两者的等级相同,罗马选择其中一个)。剩下的物品可以卖钱换取金币。罗马以 x 个硬币的价格出售任意类型的 x 级物品。

帮助罗马确定战胜 n 个怪物后预计获得的金币数量。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105; 1 ≤ k ≤ 100)。

输出

打印一个实数——战胜 n 个怪物后预期获得的金币数量。如果相对误差或绝对误差不超过 10 - 9,则认为答案是正确的。

示例

输入 #1

1 3

输出 #1

1.0000000000

输入 #2

2 1

输出 #2

2.3333333333

输入 #3

10 2

输出 #3

15.9380768924