#ddcc2016finalb. [ddcc_2016_final_b]デュアルカット
[ddcc_2016_final_b]デュアルカット
问题
半径 的晶圆被水平方向等间距切割成 等份。晶圆是用于制作某个零件的薄圆盘状物体。
为了将晶圆等间距切割成 等份,会有 条被称为切线的线条。切线从上到下依次被标记为 到 。此外,为了方便起见,我们假设图中也存在标号小于等于 或大于等于 的切线。
采用了一种名为双切割的技术来将晶圆切割为 等份。
在双切割中,我们会对切线进行多次切割。每次切割中,使用两把刀片同时切断两条切线。由于切割机器的约束,两条切线必须相隔一定距离。更准确地说,对于同时切断的两条切线的标号分别为 ,必须满足 。在这个问题中,可以多次切割同一条切线,或者切割标号小于等于 或大于等于 的切线。
当同时切割第 条和第 条切线时,切割长度由两条切线中较长的那条切线的长度表示。其中,第 条切线的长度是指在第 条切线与晶圆的共同部分上测得的线段的长度,而其他切线如第 条或第 条的长度均为 。
下面给出了机器的具体工作示例。当 , 时,机器开始运行,并将第 条和第 条切线切割,如下图(左)所示。此时,切割长度为第 条切线的长度,因为第 条切线比第 条切线更长,所以切割长度即为第 条切线的长度。切割长度以图中红色实线表示。请注意,对于类似操作,如 (如右图所示),由于不满足 ,因此无法执行。
对于每条编号为 到 的切线,至少进行一次切割即可将晶圆切割为 等份。通过巧妙地操作机器,希望能够最小化切割长度的总和。请计算切割长度的最小值。
约束条件
- 是整数
部分得分
- 对于满足 的数据集,正确回答可以获得 分。
- 对于不受任何附加约束的数据集,除了上述之外还可以额外获得 分。
输入
输入通过标准输入给出,具体格式如下。
输出
输出一个整数作为答案。允许的绝对误差或相对误差不超过 。
输入示例 1
100 4 1
输出示例 1
373.2050807569
以下是最优操作步骤之一:
- 切割第 条和 条切线
- 切割第 条和 条切线
此案例满足部分得分的约束条件。
输入示例 2
100 4 3
输出示例 2
546.4101615138
以下是最优操作步骤之一:
- 切割第 条和 条切线
- 切割第 条和 条切线
- 切割第 条和 条切线
与输入示例 1 不同,该示例中 ,因此无法同时执行切割第 条和第 条的操作,或者切割第 条和第 条的操作等,请注意机器的约束条件。
输入示例 3
43 65 12
输出示例 3
2208.8155789165
输入示例 4
1000 1000 999
输出示例 4
1570743.7385010704