#ddcc2016finalb. [ddcc_2016_final_b]デュアルカット

[ddcc_2016_final_b]デュアルカット

问题

半径 RR晶圆被水平方向等间距切割成 NN 等份。晶圆是用于制作某个零件的薄圆盘状物体。

为了将晶圆等间距切割成 NN 等份,会有 N1N-1 条被称为切线的线条。切线从上到下依次被标记为 11N1N-1。此外,为了方便起见,我们假设图中也存在标号小于等于 00 或大于等于 NN 的切线。

b7d93ccb848ebe7e3e1956b68b97625f.png

采用了一种名为双切割的技术来将晶圆切割为 NN 等份。

在双切割中,我们会对切线进行多次切割。每次切割中,使用两把刀片同时切断两条切线。由于切割机器的约束,两条切线必须相隔一定距离。更准确地说,对于同时切断的两条切线的标号分别为 i,j(i<j)i, j (i<j),必须满足 i+Mji+M ≦ j。在这个问题中,可以多次切割同一条切线,或者切割标号小于等于 00 或大于等于 NN 的切线。

当同时切割第 ii 条和第 jj 条切线时,切割长度由两条切线中较长的那条切线的长度表示。其中,第 i,(1iN1)i \\, (1 ≦ i ≦ N-1) 条切线的长度是指在第 ii 条切线与晶圆的共同部分上测得的线段的长度,而其他切线如第 00 条或第 NN 条的长度均为 00

下面给出了机器的具体工作示例。当 N=6,,M=3N=6, \\, M=3i=2,,j=5i=2, \\, j=5 时,机器开始运行,并将第 22 条和第 55 条切线切割,如下图(左)所示。此时,切割长度为第 22 条切线的长度,因为第 22 条切线比第 55 条切线更长,所以切割长度即为第 22 条切线的长度。切割长度以图中红色实线表示。请注意,对于类似操作,如 i=3,,j=5i=3,\\,j=5(如右图所示),由于不满足 i+Mji+M ≦ j,因此无法执行。

25802968adbadeb2e8567108e61a5bdd.png

对于每条编号为 11N1N-1 的切线,至少进行一次切割即可将晶圆切割为 NN 等份。通过巧妙地操作机器,希望能够最小化切割长度的总和。请计算切割长度的最小值。

约束条件

  • 1R1031 ≦ R ≦ 10^{3}
  • 2N1032 ≦ N ≦ 10^{3}
  • 1MN11 ≦ M ≦ N - 1
  • RR 是整数

部分得分

  • 对于满足 M=1M=1 的数据集,正确回答可以获得 300300 分。
  • 对于不受任何附加约束的数据集,除了上述之外还可以额外获得 400400 分。

输入

输入通过标准输入给出,具体格式如下。

RR NN MM

输出

输出一个整数作为答案。允许的绝对误差或相对误差不超过 10610^{-6}


输入示例 1

100 4 1

输出示例 1

373.2050807569

以下是最优操作步骤之一:

  • 切割第 11 条和 22 条切线
  • 切割第 00 条和 33 条切线

此案例满足部分得分的约束条件。


输入示例 2

100 4 3

输出示例 2

546.4101615138

以下是最优操作步骤之一:

  • 切割第 00 条和 33 条切线
  • 切割第 11 条和 44 条切线
  • 切割第 22 条和 55 条切线

与输入示例 1 不同,该示例中 M=3M=3,因此无法同时执行切割第 11 条和第 22 条的操作,或者切割第 11 条和第 33 条的操作等,请注意机器的约束条件。


输入示例 3

43 65 12

输出示例 3

2208.8155789165

输入示例 4

1000 1000 999

输出示例 4

1570743.7385010704