prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem E:</font> Mobile Computing</H1>3 4<p>5There is a mysterious planet called Yaen, whose space is 2-dimensional. There are many beautiful6stones on the planet, and the Yaen people love to collect them. They bring the stones back home7and make nice mobile arts of them to decorate their 2-dimensional living rooms.8</p>9<p>10In their 2-dimensional world, a mobile is defined recursively as follows:11</p>12 13<ul>14<li>  a stone hung by a string, or</li>15<li> a rod of length 1 with two sub-mobiles at both ends; the rod16  is hung by a string at the center of gravity of sub-mobiles.17  When the weights of the sub-mobiles are <i>n</i> and <i>m</i>, and their18  distances from the center of gravity are a and b respectively,19  the equation <i>n</i> &times; <i>a</i> = <i>m</i> &times; <i>b</i> holds.</li>20</ul>21<br/>22<center>23<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_mobileComputing1"><br/>24</center>25 26<p>27For example, if you got three stones with weights 1, 1, and 2, here are some possible mobiles28and their widths:29</p>30 31<center>32<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_mobileComputing2">33</center>34 35<p>36Given the weights of stones and the width of the room, your task is to design the widest possible37mobile satisfying both of the following conditions.38</p>39<ul>40   <li> It uses all the stones.</li>41   <li> Its width is less than the width of the room.</li>42</ul>43<p>44You should ignore the widths of stones.45 46</p>47 48 49<p>50In some cases two sub-mobiles hung from both ends of a rod might51overlap (see the figure on the below). Such mobiles are acceptable.52The width of the example is (1/3) + 1 + (1/4).53</p>54<br/>55<center>56  <img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_mobileComputing3"><br/>57  </center>58 59<H2>Input</H2>60 61<p>62The first line of the input gives the number of datasets. Then the specified number of datasets63follow. A dataset has the following format.64</p>65<pre>66      <i>r</i>67      <i>s</i>68      <i>w</i><sub>1</sub>69       .70       .71       .72      <i>w<sub>s</sub></i>73</pre>74 75<p>76<i>r</i> is a decimal fraction representing the width of the room, which satisfies 0 &lt; <i>r</i> &lt; 10. <i>s</i> is the77number of the stones. You may assume 1 &le; <i>s</i> &le; 6. <i>w<sub>i</sub></i> is the weight of the <i>i</i>-th stone, which is78an integer. You may assume 1 &le; <i>w<sub>i</sub></i> &le; 1000.79</p>80<p>81You can assume that no mobiles whose widths are between <i>r</i> - 0.00001 and <i>r</i> + 0.00001 can be made of given stones.82</p>83 84<H2>Output</H2>85 86<p>87For each dataset in the input, one line containing a decimal fraction should be output. The88decimal fraction should give the width of the widest possible mobile as defined above. An89output line should not contain extra characters such as spaces.90</p>91<p>92In case there is no mobile which satisfies the requirement, answer -1 instead.93</p>94<p>95The answer should not have an error greater than 0.00000001. You may output any number of96digits after the decimal point, provided that the above accuracy condition is satisfied.97 98</p>99 100<H2>Sample Input</H2>101<pre>10251031.310431051106210711081.410931101111211211132.011431151116211711181.59119412021211122112331241.714312541261127212831295130</pre>131 132<H2>Output for the Sample Input</H2>133<pre>134-11351.33333333333333351361.66666666666666671371.58333333333333351381.7142857142857142139</pre>140 141 142 143 144