Preparing NOJ

玻璃球 【深蓝】

10000ms 65536K

Description:

玩过玻璃球游戏吗?sed同学小学没有毕业之前玩过,他常常用一个直径为d的圆柱管来装玻璃球,已知每个玻璃球是半径为 r1, r2, . . . , rn的球体,他当时一直有一个疑问:装这些玻璃球最少需要多长的圆柱管。现请你帮他解决这个问题。

假设玻璃球半径充分大,以至于管中不存在三个可以同时相互接触的玻璃球。给定这样的限制,表示玻璃球将总以这样的方式装入:他们的中心点位于含导管旋转轴的2维平面上。

Input:

输入包含多个测试例。每个测试例包括两行。每个测试例的第一行包含一个整数n (1 ≤ n ≤ 15) ,表示sed持有玻璃球的数目,还有一个浮点值d (2.0 ≤ d ≤ 1000.0) ,表示管子直径。两值以空格隔开。每个测试例的第二行包含n个由空格分隔的浮点数r1 r2 . . . rn(1.0 ≤ ri ≤ d/2) ,为sed玻璃球的半径。一个空白行分隔所以输入测试例。一行“0 0”表示输入结束,无需处理此例。

Output:

对于每个输入测试例,打印管子的最短长度,结果取整。

Sample Input:

2 98.1789
42.8602 28.7622

3 747.702
339.687 191.953 330.811

0 0

Sample Output:

138
1628

Note:

本题由旧版NOJ导入,来源:“IBM南邮杯”团队赛2009

Info

NOJ

Provider NOJ

Code NOJ1118

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet