← 返回题目列表

AtCoder · ddcc_2016_final_b

B. 双切

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

配点 : 700 点

問題文

半径 R 的晶圆水平 用等間隔剪切 N 我决定把它分开。晶圆是一种薄的盘状物体,用于制造某些零件。

均匀分布的晶圆 N 用于分割剪线 名为的行 N-1 我有一本书。 从顶部到切割线 它的编号为 1 ~ N-1 。 另外,如下图所示 0 以下 N 为了方便起见,我们还将假设存在具有上述数字的切割线。

b7d93ccb848ebe7e3e1956b68b97625f.png

晶圆 N 划分双切 我决定使用方法。

使用双切割时,切割操作会在切割线上执行多次。 在 1 剪辑中,2 使用两个刀片 2 同时剪切书籍的剪切线。 由于切割机器的限制,2 书籍的切割线必须间隔一定的距离。 更准确地说,同时切割 2 书上每行剪切行号 i,j (i<j) 必须满足i+M ≦ j 。 在这个问题中,同样的切割线 如果断开连接超过 2 次,0 以下 N 您可以在上面数字的切割线处进行切割。

i 数量和 j 同时切割切割线时切割长度是 可以通过兑换2 表示为书籍剪切线的较长长度。 这里 i \, (1 ≦ i ≦ N-1) 切割线的长度是多少? i 这是由编号的切割线表示的直线与晶圆的公共部分之间的线段的长度。 0 巴尼亚 N 等切割线的长度为 0 。

机器操作的具体示例如下所示。 当N=6, \, M=3 当您以 i=2, \, j=5 运行机器时,它将如下图(左)所示。 将剪切编号为 2 数量和 5 的剪切线。此时的切割长度为 编号为 2 的切割线是 因为它比剪切行号 5 长, 这是编号为2 的切割线的长度。切割线的长度由图中的红色实线表示。 这里,如下图(右) 诸如 i=3,\,j=5 之类的操作 请注意,这是无法完成的,因为它不满足 i+M ≦ j 。

25802968adbadeb2e8567108e61a5bdd.png

1 ~ N-1 每条切割线 1 如果晶圆切割超过 N 可以分割。 通过熟练操作机器,可以将晶圆 N 我想在分割时最小化总切割长度。 求总切割长度的最小值。 如果正确答案是满足

制約

  • 1 ≦ R ≦ 10^{3}
  • 2 ≦ N ≦ 10^{3}
  • 1 ≦ M ≦ N - 1
  • R 是一个整数

部分点

  • M=1 的数据集,300 点。
  • 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 400 点。

入力

输入是按以下格式从标准输入给出的。

R N M

出力

答案 输出为 1 行。绝对误差或相对误差 10^{-6} 或更少是可以接受的。


入力例 1

100 4 1

出力例 1

373.2050807569

最佳切割程序如下: 1 一。 剪切编号为

  • 1 数量和 2 的剪切线
  • 0 数量和 3 的剪切线

这种情况满足部分点约束。


入力例 2

100 4 3

出力例 2

546.4101615138

最佳切割程序如下: 1 一。 剪切编号为

  • 0 数量和 3 的剪切线
  • 1 数量和 4 的剪切线
  • 2 数量和 5 的剪切线

M 是一个示例输入 与 1 不同 3 ,所以1 数量和 2 可以同时切割, 请注意,由于机器限制,无法指定同时切割1 数量和 3 数量。


入力例 3

43 65 12

出力例 3

2208.8155789165

入力例 4

1000 1000 999

出力例 4

1570743.7385010704