There is a mysterious planet called Yaen, whose space is 2-dimensional. There are many…
- User
There is a mysterious planet called Yaen, whose space is 2-dimensional. There are many beautiful stones on the planet, and the Yaen people love to collect them. They bring the stones back home and make nice mobile arts of them to decorate their 2-dimensional living rooms.
In their 2-dimensional world, a mobile is defined recursively as follows:
- a stone hung by a string, or
- a rod of length 1 with two sub-mobiles at both ends; the rod is hung by a string at the center of gravity of sub-mobiles. When the weights of the sub-mobiles are n and m, and their distances from the center of gravity are a and b respectively, the equation n × a = m × b holds.
For example, if you got three stones with weights 1, 1, and 2, here are some possible mobiles and their widths:
Given the weights of stones and the width of the room, your task is to design the widest possible mobile satisfying both of the following conditions.
- It uses all the stones.
- Its width is less than the width of the room.
You should ignore the widths of stones.
In some cases two sub-mobiles hung from both ends of a rod might overlap (see the figure on the below). Such mobiles are acceptable. The width of the example is (1/3) + 1 + (1/4).
The first line of the input gives the number of datasets. Then the specified number of datasets follow. A dataset has the following format.
r s w1 . . . ws
r is a decimal fraction representing the width of the room, which satisfies 0 < r < 10. s is the number of the stones. You may assume 1 ≤ s ≤ 6. wi is the weight of the i-th stone, which is an integer. You may assume 1 ≤ wi ≤ 1000.
You can assume that no mobiles whose widths are between r - 0.00001 and r + 0.00001 can be made of given stones.
Output
For each dataset in the input, one line containing a decimal fraction should be output. The decimal fraction should give the width of the widest possible mobile as defined above. An output line should not contain extra characters such as spaces.
In case there is no mobile which satisfies the requirement, answer -1 instead.
The answer should not have an error greater than 0.00000001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.
Example
Input
5 1.3 3 1 2 1 1.4 3 1 2 1 2.0 3 1 2 1 1.59 4 2 1 1 3 1.7143 4 1 2 3 5
Output
-1 1.3333333333333335 1.6666666666666667 1.5833333333333335 1.7142857142857142
Assistant
We need to compute maximum possible width of a mobile constructed using all stones (exactly once) as leaves, obeying the physics of balance: a rod of length 1 (so ends are at distance 0.5 from the center of the rod? Wait: rod length is 1; it is hung by a string at the center of gravity of sub-mobiles. When weights are n and m, and distances from the center of gravity are a and b respectively, we have na = mb. But the rod is of length 1, so the distance between the two attachment points of sub-mobiles is 1. Actually, we need to interpret geometry.
In the mobile definition: There is a rod of length 1 with two sub-mobiles at both ends; the rod is hung by a string at the center of gravity of sub-mobiles. The center of gravity is somewhere along the rod, between the two endpoints. Let the left sub-mobile have total weight L, right sub-mobile total weight R. Let the center of gravity be at distance x from the left endpoint and (1 - x) from the right endpoint. The balance condition: L * x = R * (1 - x). Actually careful: The torque about the hanging point must be zero: L * (distance from left attachment to CG) = R * (distance from right attachment to CG). The distances from the attachments to the hanging point: The left sub-mobile is attached at left endpoint; its weight acts downward at that point. The rod is rigid, so the moment arm about the hanging point is the horizontal distance from left endpoint to hanging point. Similarly for right. So if hanging point (center of gravity) is at distance a from left endpoint, then distance from right endpoint is b = 1 - a. Then equilibrium: L * a = R * b. That matches the statement: "When the weights of the sub-mobiles are n and m, and their distances from the center of gravity are a and b respectively, the equation n × a = m × b holds." So a and b are distances from the sub-mobiles to the hanging point. So indeed a + b = 1.
Thus given two sub-mobiles with total weights L and R, we can compute the hanging point offset a (distance from left attachment to CG) = R / (L + R) because from La = R(1-a) => La = R - Ra => a*(L+R) = R => a = R/(L+R). Similarly b = L/(L+R). Note that a and b are distances from left and right ends to the CG, respectively.
Now the width of a mobile: It is presumably the horizontal span from leftmost point to rightmost point when hung from the top? We need to define width. For a stone hung by a string, it's just a point? But the problem says "ignore the widths of stones." So each stone contributes zero width as an object. However, the mobile consists of rods and strings. The width is the total horizontal distance between the leftmost and rightmost positions of the stones? Or maybe it's the horizontal span of the entire structure when hung? Let's check examples.
Given three stones with weights 1,1,2, they show some possible mobiles and their widths. The examples: "here are some possible mobiles and their widths: (figure)." We need to infer the width definition.
From text: "It uses all the stones. Its width is less than the width of the room." So the width is like the overall width of the mobile when hung. They ignore stone widths, so it's about distances between endpoints of rods.
In the sample output: Input 1.3 with three stones 1,2,1 gave output -1 (no mobile) but for 1.4 it gave 1.33333... For 2.0 it gave 1.66666... For 1.59 with stones 2,1,1,3 gave 1.58333... So we need to compute width.
Let's try to deduce width definition.
Consider two stones weights n and m attached directly to a rod? Actually a mobile is built recursively: either a single stone (hung by a string) -> that would be just a point? The width of a single stone mobile? Possibly 0? But if it's 0, then any combination of stones could be built trivially? That can't be because they need width less than room, and there is max width. So single stone mobile must have some width? Hmm.
But the definition: "a stone hung by a string" is a mobile. But then what is its width? Possibly the stone itself has zero width but the string is vertical, so the horizontal extent is just the stone's point? They say ignore widths of stones, so maybe it's considered as a point mass. So width of such a mobile would be 0. However, then a mobile using all stones could be made by attaching each stone individually to separate strings? That would be multiple independent mobiles, not one mobile. But we need one mobile that uses all stones. The definition allows recursive combination. So final mobile is a tree structure with stones as leaves, rods internal nodes, and the topmost string hangs from the ceiling.
Thus the width is the distance between the leftmost and rightmost leaf positions in the final configuration? Or maybe it's the total horizontal span from leftmost point to rightmost point of the entire structure, which includes the rods? Since rods have length 1, and sub-mobiles may extend further outward.
Typically, in a mobile, each sub-mobile hangs below its attachment point. So the horizontal positions of stones are determined by the geometry of rods. The width is the maximum difference in x-coordinates of any point on the mobile.
But careful: The rods are hung at their center of gravity. So the rod is horizontal? Usually in mobiles, rods are horizontal because they are balanced. The hanging point is directly above the center of mass of the system below. If the rod is horizontal, then the left and right attachments are at equal vertical level. But sub-mobiles hang from those points, possibly causing offsets. However, the problem statement says: "a rod of length 1 with two sub-mobiles at both ends; the rod is hung by a string at the center of gravity of sub-mobiles." It does not explicitly say the rod is horizontal, but in typical mobile it is, because the string attaches at the balance point and the rod rotates freely, so it will be horizontal if the torques balance. So we assume the rod is horizontal.
Given that, the geometry: The top rod of length 1, horizontal. Its left endpoint at some x coordinate, right endpoint at x+1. The hanging point (string attach) at some x + a where a = R/(L+R) from left (since from left endpoint to CG). So the left sub-mobile hangs from left endpoint, and its own width will extend leftwards and rightwards relative to that point. Similarly, right sub-mobile hangs from right endpoint. The overall width is the span from leftmost extent to rightmost extent.
Because sub-mobiles can overlap: if left sub-mobile extends to the right beyond the left endpoint, and right sub-mobile extends to the left beyond the right endpoint, they may overlap. Overlap is allowed. So the overall width is not simply the sum of widths of left and right sub-mobiles plus 1? Actually we need to compute the extremes.
We need to formalize the width of a mobile given its structure.
Let’s define for a mobile M: it has a total weight W (sum of leaf weights). When hung, the point from which it hangs (the attachment point at the top) is the balance point. The mobile extends left and right from that hanging point.
Define for a mobile M:
- Its total weight: weight(M).
- Its left extent (the maximum distance to the left of the hanging point that any part of M reaches). Let's call L_ext (non-negative).
- Its right extent (maximum distance to the right of the hanging point): R_ext (non-negative).
Then the overall width = L_ext + R_ext.
But careful: For a single stone hung by a string, the hanging point is directly above the stone? Actually a stone hung by a string: the string attaches to the stone? Typically a stone hung by a string means the string is attached to the stone and then to the ceiling. But in mobiles, usually there is a string attached to the rod; for a leaf it's just the stone. But the definition says "a stone hung by a string" is a mobile. So that mobile consists of a stone at the end of a string. The hanging point is where the string is attached to the ceiling. The stone is directly below (vertical). So the horizontal position of the stone is exactly below the hanging point (if string is massless and vertical). So the stone's x-coordinate equals the hanging point's x-coordinate. Then the left extent and right extent from hanging point are both 0 (since the stone is directly below, no horizontal offset). But could there be any width? Probably 0. However, if we ignore stone width, the mobile occupies just a vertical line. So width = 0. But then combining stones would produce some width.
But let’s check examples: For three stones 1,2,1, we got output 1.33333 for room width 1.4, and 1.66666 for room width 2.0. If single stone width is 0, then the maximum possible width from a combination of three stones would be something like maybe 1.5? Let's compute possibilities.
We need to interpret width from given sample outputs.
Better approach: Search known problem. This is from ACM ICPC? Possibly "Yaen" problem? Let's search memory: There's a known problem "Mobile" or "Mobiles" maybe from IOI? Not sure.
Alternatively, we can derive the width formula.
Consider a mobile made of two sub-mobiles A and B, combined by a rod of length 1.
Let for sub-mobile A: total weight = wA, left extent = lA (distance from its hanging point to leftmost point), right extent = rA (distance from its hanging point to rightmost point). Its hanging point is the point where the string attaches to the rod. For A, its top attachment point is at the left end of the rod. So relative to that attachment point, the mobile A extends left by lA and right by rA.
Similarly for B: wB, lB, rB; its attachment point is at the right end of the rod.
Now, the rod itself: length 1. The left attachment point is at some x coordinate; the right attachment point at x+1. The top hanging point (where the rod's string attaches) is at the center of gravity of the combined system. Its distance from left attachment is a = wB/(wA+wB) and from right attachment is b = wA/(wA+wB). So the hanging point is at x + a.
Now we need to compute the leftmost and rightmost points of the entire mobile relative to the top hanging point.
Coordinates: set top hanging point as 0.
Let the left attachment point be at coordinate? It is on the rod: distance a from hanging point? Since hanging point is at the CG. The left attachment is distance a to the left? Actually if hanging point is between the two ends, and a is distance from left end to hanging point, then left end is a units left of hanging point. So coordinate of left attachment = -a. Similarly, right attachment is at distance b to the right: coordinate = b (since b = 1 - a, and a+b=1). Check: from left end to hanging point = a, so left end is to the left of hanging point by a. So coordinate = -a. Right end is to the right by b: coordinate = b.
Thus left sub-mobile A is attached at x = -a. Its own structure relative to its hanging point (which is at -a) has left extent lA (to the left) and right extent rA (to the right). So relative to the top hanging point, the leftmost point of A is at -a - lA. The rightmost point of A is at -a + rA.
Similarly for B: attached at x = b. So its leftmost is at b - lB, rightmost at b + rB.
Thus overall leftmost = min( -a - lA, b - lB, maybe also -a? Actually the rod itself might extend? But rod ends are at -a and b; but those points are covered by the attachments; the rod itself might have length but it's just a line segment from -a to b, which is within the extremes given by the attachments and sub-mobiles? Possibly the rod itself could be the leftmost if there are no sub-mobiles extending beyond? But sub-mobiles are attached at ends, and rod extends from -a to b. So the leftmost could be -a if lA=0 (stone only) and -a is leftmost; but if lA>0, leftmost might be -a - lA. So overall leftmost = min(-a - lA, b - lB, -a, b)? However -a is >= -a - lA? Actually lA >=0, so -a - lA <= -a. So leftmost is the more negative of -a - lA and b - lB. But b - lB could be negative if lB > b? Possibly. So overall leftmost = min( -a - lA, b - lB ). Also consider the rod itself: its left end is at -a, but since -a >= -a - lA, it is not more left. Similarly, right end is at b but b <= b + rB. So overall rightmost = max( -a + rA, b + rB ).
Thus total width = (rightmost - leftmost) = max( -a + rA, b + rB ) - min( -a - lA, b - lB ).
Alternatively, we can define left extent L = max( a + lA? Wait careful: left extent from top hanging point is the distance to leftmost point, which is - leftmost if leftmost negative. But we can treat symmetrically.
Given this definition, the width is determined by the extents of the sub-mobiles.
Now, for a leaf (stone): what are l and r? As argued, stone hung by string: its hanging point is at the top of the string, the stone is directly below. So relative to its hanging point, the stone is at (0, below). Since stones have zero width, the leftmost and rightmost points are at 0. So l=0, r=0. Thus leaf mobile: weight = w, left_extent = 0, right_extent = 0.
But wait, could there be any width from the rod? No rod at leaf.
Thus a single stone mobile has width 0.
Now, if we combine two stones of equal weight, say both weight 1, into a rod: wA=1, wB=1 => a = 1/(1+1)=0.5, b=0.5. For each leaf: lA=rA=0, lB=rB=0. Then leftmost = min(-0.5 - 0, 0.5 - 0) = min(-0.5, 0.5) = -0.5. Rightmost = max(-0.5+0, 0.5+0)= max(-0.5,0.5)=0.5. Width = 1.0. So such a mobile would have width 1.0. That makes sense: a rod of length 1 balanced in the middle gives width 1. So two equal stones produce width 1.
But sample outputs: For three stones 1,2,1, we got width 1.33333 and 1.66666. Let's test constructing mobiles with three stones.
We have stones 1,2,1. Possible tree structures: Since s ≤ 6, we can enumerate.
One structure: Combine stone 1 and stone 2 into a sub-mobile, then combine that with stone 1. Let's compute.
Case 1: First combine left stone weight 1 and right stone weight 2 with rod. Then combine resulting mobile (weight 3) with another stone weight 1 as the other sub-mobile.
- Sub-mobile A (from 1 and 2): wA = 3. But need to know its extents lA, rA. That depends on how we arranged the two stones inside A. But A is a mobile made of two stones. The structure of A: we have two leaves, but we could also have them combined in different order? Actually for two stones, the only way is to hang them on a rod. But we could choose which stone is left and which is right. That affects extents? For a two-stone mobile, l and r are symmetric? Let's compute.
Suppose we take A: left stone weight w1, right stone weight w2. For A, its hanging point is at some offset aA = w2/(w1+w2) from left endpoint. So the leftmost point of A is at -aA (since left stone is at left endpoint, but leaf has zero extent; however left endpoint itself is at -aA from hanging point, and leaf is at that point? Actually careful: For mobile A, its hanging point is at the top string. Its left attachment point is at distance aA to the left? Actually we defined a as distance from left attachment to hanging point. So left attachment is at -aA from hanging point. The left stone is attached at left endpoint, so its position is at -aA relative to A's hanging point. Since leaf has zero extent, the leftmost point of A is at -aA (same as left attachment). Similarly, the rightmost point is at bA = w1/(w1+w2) from hanging point (since right attachment is at +bA). So for A, left_extent lA = aA (distance from hanging point to leftmost point) because leftmost point is at -aA, so distance to left is aA. Right_extent rA = bA. Actually we defined l and r as distances to left and right extremes from hanging point. So for a simple two-stone mobile, l = a, r = b. But careful: a = R/(L+R) where L is left weight, R is right weight. So if left weight is w1, right weight is w2, then a = w2/(w1+w2) and b = w1/(w1+w2). So leftmost is at distance a to the left, rightmost at distance b to the right. So width = a + b = 1. But note that the leftmost point is exactly at left attachment, not beyond, because leaf has zero width.
Thus for A: wA = w1+w2, lA = a (the distance from hanging point to left endpoint), rA = b.
But note: In our combination of two mobiles, we have lA and rA as distances from A's own hanging point to leftmost and rightmost points. That seems consistent: For a leaf, lA=0, rA=0. For a rod combining two sub-mobiles, we can compute l and r recursively.
Now, for the combination of A and B (two mobiles) into a top rod, we derived:
Let wA, lA, rA; wB, lB, rB.
Given rod length = 1, hanging point offset from left attachment a = wB/(wA+wB), b = wA/(wA+wB).
Coordinates: left attachment at -a, right attachment at b.
Now, leftmost of A relative to A's hanging point (which is at left attachment) is at -lA (since lA is distance to left; careful: lA defined as left extent from hanging point, so the leftmost point is at position -lA relative to A's hanging point). Similarly, rightmost of A is at +rA relative to A's hanging point.
Thus relative to top hanging point, A's leftmost = -a - lA. Similarly, A's rightmost = -a + rA.
For B: leftmost = b - lB, rightmost = b + rB.
Overall leftmost = min(-a - lA, b - lB). Overall rightmost = max(-a + rA, b + rB).
Thus total width = (rightmost - leftmost). And the left extent from top hanging point (L_ext) = - leftmost if leftmost negative, but we don't need separately.
Now compute extents for combined mobile relative to its hanging point: left_ext = max distance to left (positive) = - overall leftmost if overall leftmost negative? Actually if leftmost is negative, then left extent = - leftmost (since hanging point is at 0). If leftmost is positive (i.e., everything to the right), then left_ext=0. But from symmetry? Usually leftmost may be negative, rightmost positive. But could be all on one side? Possibly if one sub-mobile is very heavy and the hanging point is near one end, the other end might be all on one side? Actually because the rod is of fixed length, and sub-mobiles may extend further outward, the overall leftmost could be negative, rightmost positive. So width = left_ext + right_ext, but careful: if both extremes are on same side, width is just difference. But from typical mobile, they'll be on both sides.
Now we can compute for given combination of stones.
Back to sample: stones 1,2,1. Let's enumerate possible binary tree structures (since mobile is a full binary tree with leaves as stones). There are 2 possible binary trees for 3 leaves (catalan number C2=2). Actually with 3 leaves, there is essentially one shape: a root rod with left and right subtrees; one of the subtrees is a leaf, the other is a rod with two leaves. So two possibilities: left subtree is a leaf (weight 1) and right subtree is a mobile of (2,1) or (1,2) depending on arrangement; or left subtree is a mobile of (1,2) and right subtree is a leaf (1). Also the order of leaves matters because weights matter. So we need to consider all full binary trees with labeled leaves? Actually stones are distinct by weight, but weights are given; we assign each stone to a leaf. So we must consider all assignments and tree structures.
However, the sample outputs give two widths: 1.33333 and 1.66666. Possibly these correspond to the maximum width less than some thresholds.
But note that for room width 1.3, answer -1, meaning no mobile with width < 1.3 exists using all stones? For room width 1.4, max width is 1.33333, which is <1.4. For room width 2.0, max width is 1.66666, which is <2.0. So the maximum possible width over all mobiles made from these stones is 1.66666? Actually there might be a mobile with width 1.66666, and maybe also one with 1.5 etc. But the max is 1.66666. So for room width 2.0, we can achieve max 1.66666, which is less than 2.0, so answer is 1.66666. For room width 1.4, we need the widest possible that is <1.4; maybe the maximum overall width is 1.66666 but it's not <1.4, so we need the next best: maybe there is a configuration with width 1.33333 that is <1.4, and maybe also one with width 1.25? But the answer is 1.33333, so that's the widest under 1.4. For room width 1.3, the widest under 1.3 is perhaps 1.25? But answer -1, so maybe no mobile with width <1.3 exists, meaning all possible mobiles have width >= 1.33333? Or maybe the only possible widths are 1.33333 and 1.66666, both > 1.3, so none qualify. That would match: possible widths are 1.33333 and 1.66666; both >1.3, so no mobile under 1.3 -> -1.
Thus we need to confirm that for three stones 1,2,1, the only possible widths are 4/3 ≈1.33333 and 5/3 ≈1.66667? Actually 1.66666 is 5/3? 5/3 = 1.66666..., yes. 4/3 = 1.33333... So those are plausible rational numbers.
Let's test: If we combine stone 1 and stone 2 into a sub-mobile, and then combine with the other stone 1.
Option 1: Sub-mobile A consists of left stone 1 and right stone 2. Then wA=3. Compute lA, rA: For A, with left weight 1, right weight 2: a_A = w_right/(w_left+w_right)=2/3, b_A = w_left/(sum)=1/3. So leftmost of A is at distance a_A = 2/3 to left of its hanging point, rightmost at distance b_A = 1/3 to right. So lA = 2/3, rA = 1/3.
Now top rod: combine A (weight 3) with B (stone weight 1). There are two possibilities: A on left, B on right; or B on left, A on right. Let's consider A left, B right. Then wA=3, lA=2/3, rA=1/3; wB=1, lB=0, rB=0.
Compute a_top = wB/(wA+wB) = 1/4? Actually a is distance from left attachment to hanging point. If left is A, right is B, then a = weight of right / total = 1/4, b = weight of left / total = 3/4. So a=0.25, b=0.75.
Now compute overall leftmost = min( -a - lA, b - lB ) = min( -0.25 - 2/3, 0.75 - 0 ) = min( -0.25 - 0.6666667 = -0.9166667, 0.75 ) = -0.9166667. Rightmost = max( -a + rA, b + rB ) = max( -0.25 + 1/3 = -0.25+0.33333=0.08333, 0.75+0=0.75 ) = 0.75. Width = 0.75 - (-0.9166667) = 1.6666667. That matches 5/3.
Now consider A on right, B on left: So left is B (weight 1, l=0,r=0), right is A (weight 3, lA=2/3, rA=1/3). Compute a = w_right/(total) = 3/4? Wait careful: a = distance from left attachment to hanging point = weight of right / total? Actually formula: a = w_right/(w_left + w_right). Because left weight * a = right weight * (1-a) => a = w_right/(w_left + w_right). Yes. So if left weight is wB=1, right weight is wA=3, then a = 3/4, b = 1/4. So a=0.75, b=0.25.
Now leftmost = min( -a - lB, b - lA ) = min( -0.75 - 0 = -0.75, 0.25 - (2/3) = 0.25 - 0.6666667 = -0.4166667 ) = -0.75? Actually min(-0.75, -0.4167) = -0.75. Rightmost = max( -a + rB, b + rA ) = max( -0.75+0 = -0.75, 0.25 + (1/3)=0.25+0.33333=0.58333 ) = 0.58333. Width = 0.58333 - (-0.75) = 1.33333. That's 4/3. So indeed two possible widths: 4/3 and 5/3. That matches sample.
Thus our width definition matches sample.
Now note: In the first scenario (A left, B right) we got width 5/3; in second we got 4/3. So the width depends on ordering of subtrees.
Now we also need to consider the alternative tree: combine the two 1's first, then combine with 2. That yields other widths? Let's test: Sub-mobile C: combine left 1 and right 1. Then wC=2. For C: left weight=1, right=1 => a = 1/2, b=1/2. So lC = a = 0.5, rC = b = 0.5. Then combine with stone weight 2. Two arrangements: C left, 2 right; and 2 left, C right.
Case C left, 2 right: wC=2, lC=0.5, rC=0.5; wD=2? Actually stone weight 2, so wD=2, lD=0, rD=0. But careful: stone weight 2 is leaf. So w=2, l=0, r=0. Now total weight =4. a = w_right/(total)=2/4=0.5, b = w_left/(total)=2/4=0.5. So a=0.5, b=0.5. Then leftmost = min( -a - lC, b - lD ) = min( -0.5-0.5=-1.0, 0.5-0=0.5 ) = -1.0. Rightmost = max( -a + rC, b + rD ) = max( -0.5+0.5=0.0, 0.5+0=0.5 ) = 0.5. Width = 1.5. That's 1.5.
Case 2 left, C right: left is stone weight 2 (l=0,r=0), right is C (w=2,lC=0.5,rC=0.5). a = w_right/(total) = 2/4=0.5, b = w_left/(total)=2/4=0.5 (same). leftmost = min( -0.5-0 = -0.5, 0.5 - 0.5 = 0.0 ) = -0.5. rightmost = max( -0.5+0 = -0.5, 0.5+0.5=1.0 ) = 1.0. Width = 1.5. So both give width 1.5? Wait compute second: leftmost = min(-0.5, 0.5-0.5=0) = -0.5; rightmost = max(-0.5, 1.0)=1.0; width = 1.5. Yes.
So with grouping (1+1) then 2 gives width 1.5. But we didn't see 1.5 in sample? For room width 1.4, max under 1.4 is 1.33333, not 1.5 because 1.5 > 1.4. For room width 2.0, max is 1.66666, which is >1.5, so why is the answer 1.66666 not 1.5? Because we can get 1.66666, which is larger than 1.5, and still less than 2.0. So maximum width overall for these stones is max over all trees and assignments: from earlier we have 5/3 ~1.66666, also 4/3 ~1.33333, and 1.5. So max is 1.66666. So for room width 2.0, answer is 1.66666, as given. For room width 1.4, the widest mobile less than 1.4 would be max of {1.33333, maybe 1.5? 1.5 >1.4 so not allowed, so 1.33333 is best. For room width 1.3, none are ≤1.3? 1.33333>1.3, 1.5>1.3, 1.66666>1.3, so no valid, answer -1. So consistent.
Thus our width formula seems correct.
Now we need to solve the problem: given a list of stone weights (s up to 6) and a room width r (float), find the maximum possible width of a mobile using all stones exactly once, that is less than r. If none, output -1.
We need to consider all possible full binary trees with s leaves (Catalan number for s=6 is 132) and all assignments of stones to leaves (s! permutations) and all possible ways to assign left/right orientation at each internal node? Actually the tree structure is binary, but for each internal node we have two children: left and right matter because swapping left and right changes a and b, thus width. So we need to consider both orderings. So essentially each binary tree with labeled leaves (each leaf assigned a distinct stone) and with ordered children (left/right) determines a mobile. So total possibilities: For each unordered full binary tree (shape), we assign s distinct leaves (stone weights) to the leaves (s! assignments). Then for each internal node, we can optionally swap left/right? Actually the tree shape already has left/right order? Typically binary trees are ordered (left/right distinct). The number of full binary trees with n leaves where internal nodes are unlabeled and left/right matters is the Catalan number C_{n-1}. For n=3, C2=2; indeed we had two ordered trees: ((1,2),3) and (1,(2,3)) but note (1,(2,3)) is different from ((2,3),1) etc. Actually for n=3, the two ordered trees are: ( (leaf, leaf), leaf ) and ( leaf, (leaf, leaf) ). That's what we used. And for each such tree, the assignment of which leaf gets which weight yields different mobiles. And also for each internal node, swapping left/right after assignment? But that's already captured by the ordered tree structure: the tree defines which subtree is left and which is right. If we consider unordered trees, we would also consider flipping at nodes as distinct configurations. However, it's easier to generate all binary trees where internal nodes are binary, and for each node we consider both orders (or treat left/right as part of the tree). Since we will generate recursively, we can consider for each subset of stones we choose a left subset and a right subset (partition into two non-empty subsets) and then recursively compute all possible mobiles from left subset and right subset, and then combine them in two ways: left as left child, right as right child; and also the opposite: left as right child, right as left child. But careful: When we partition, order matters? Actually if we treat left and right as distinct, then each unordered partition yields two ordered pairs. However, note that recursive construction will generate each ordered combination once if we consider all ways to split the set into two ordered subsets. Since stones are distinct (by weight, but weights can be equal? They are integers, could be duplicates. But the stones are distinct objects? The problem says "weights of the stones", not that stones are distinguishable beyond weight. However, if two stones have same weight, swapping them yields the same mobile configuration? Possibly yes because weights are identical, but the stones themselves are physically distinct? The problem says "Given the weights of stones", we have a multiset of weights. The stones are probably considered identical except weight. But does labeling matter? In the examples, with weights 1,2,1, there are two identical weight-1 stones. When enumerating mobiles, different assignments of the two 1's to leaves could produce same width? But it's okay to treat them as distinct for enumeration and then consider duplicates; but we can also treat them as multiset and avoid duplicates. But given s ≤ 6, we can simply treat stones as distinct by index, and after computing widths, we might get duplicate values; but that's fine. We just need to compute maximum width less than r.
However, we need to be careful: Are stones considered distinct? The input lists weights w1..ws. They may have duplicates. For computing all possible mobiles, the arrangement of stones with identical weights might produce same width, but we still need to consider all distinct assignments? Actually if two stones have same weight, swapping them yields identical physical configuration (since only weight matters for balance and width? The actual positions depend only on the weights, not on identity. So the resulting width is determined by the multiset of weights in each subtree. Therefore, it's sufficient to consider the multiset of weights in each subtree, not which specific stone is where, as long as weights are same. So we can use DP over subsets (bitmask) of stones (since s ≤ 6, we can use bitmask with 6 bits, up to 64 states). For each subset, we compute all possible (weight, left_extent, right_extent) triples that can be achieved by a mobile using exactly those stones. But note that left_extent and right_extent are distances from the hanging point to leftmost and rightmost points, and they are not independent; they depend on the internal structure.
We can represent a mobile by (W, L, R) where W is total weight, L is left extent (distance to leftmost point from hanging point), R is right extent (distance to rightmost point from hanging point). For a leaf (single stone), we have (w, 0, 0).
For combining two mobiles A and B into a new mobile C, we have two possibilities: A as left child, B as right child; or B as left, A as right. But note that the order matters because of the orientation of the rod. So we generate two possible C for each ordered pair (A, B). For each combination, we compute:
Given A: (wA, LA, RA) and B: (wB, LB, RB). The new mobile's weight wC = wA + wB.
Compute a = wB / (wA + wB) // distance from left attachment to hanging point b = wA / (wA + wB) // distance from right attachment to hanging point? Actually b = 1 - a, but since a = wB/(wA+wB), b = wA/(wA+wB). Yes.
Now, the left attachment point (where A hangs) is at coordinate -a relative to C's hanging point. The right attachment point is at coordinate +b.
Then leftmost point from C: min( -a - LA, b - LB ) // careful: b - LB? Actually B's leftmost relative to its hanging point is at -LB (since left extent LB means leftmost is at -LB from its hanging point). B's hanging point is at +b, so its leftmost is at b - LB. Yes. Similarly rightmost: max( -a + RA, b + RB ).
Thus L_ext = - leftmost if leftmost negative else 0? Actually the leftmost might be positive (if everything is to the right), but given the structure, it's likely negative. But to be safe, we can compute width = rightmost - leftmost. And the left extent and right extent relative to C's hanging point can be computed as: Lc = max(0, -leftmost)?? Actually we need to store Lc and Rc for future combinations? For further combination as a sub-mobile, we need the left extent and right extent from its own hanging point. After computing leftmost and rightmost, we can define: Lc = - leftmost (if leftmost < 0) else 0? But is it possible leftmost > 0? That would mean the entire mobile is to the right of hanging point. Could that happen? Suppose A and B are both such that they extend only to the right, and the left attachment is to the right of hanging point? But the left attachment is at -a, which is negative (since a>0). So -a is negative. So leftmost from A includes -a - LA, which is more negative. So leftmost is certainly negative because -a - LA ≤ -a < 0. Similarly, b - LB could be negative if LB > b, but it could be positive if LB < b. However, the min of negative and possibly positive is negative because -a - LA is negative. So leftmost will always be negative. Because -a - LA is negative (since a>0, LA≥0). So leftmost is negative. Similarly, rightmost will be positive because b + RB ≥ b > 0 (since b>0). So overall the hanging point is somewhere inside the span, with leftmost negative, rightmost positive. So width = rightmost - leftmost = (rightmost) + (-leftmost). So we can compute Lc = - leftmost, Rc = rightmost. Then width = Lc + Rc. And these Lc and Rc are the left and right extents of mobile C relative to its hanging point. Indeed Lc = distance from hanging point to leftmost point, Rc = distance to rightmost point.
Thus we can compute: Lc = max( a + LA, b - LB? Wait careful: leftmost = min( -a - LA, b - LB ). Since -a - LA is negative, its absolute value is a + LA. b - LB could be positive or negative; if it's negative, its absolute would be LB - b. But we need the maximum distance to the leftmost point on the left side. Actually Lc should be the distance to the leftmost point, which is - leftmost if leftmost is negative. So Lc = - min( -a - LA, b - LB ) = max( a + LA, -(b - LB) )? Let's derive properly.
Let leftmost = min( X, Y ) where X = -a - LA, Y = b - LB. Since X is negative, Y may be negative or positive. The leftmost is the smaller (more negative) of X and Y. The distance from hanging point to leftmost is -leftmost if leftmost negative, but if leftmost is positive, that would be weird. However, as argued, X is negative, so leftmost ≤ X < 0. So leftmost is negative. So Lc = - leftmost = - min(X, Y) = max( -X, -Y )? Actually min of two numbers: m = min(X,Y). Then -m = max(-X, -Y). Because multiplying by -1 reverses order. So Lc = max( -X, -Y ) = max( a + LA, - (b - LB) ) = max( a + LA, LB - b ). Since LB - b could be negative? Actually LB - b may be negative if LB < b, then max( a+LA, LB-b ) could be a+LA, which is positive. But is LB - b the distance from hanging point to the point b - LB if that point is left of hanging point? Let's think geometrically.
Better to compute directly: Lc = max( a + LA, max(0, LB - b)? ) Hmm.
Actually simpler: we can compute Lc as the maximum distance to the left among the two sub-mobiles when transformed to the top coordinates. The leftmost point's distance to the hanging point (positive if left) is max( distance from hanging point to leftmost of A, distance from hanging point to leftmost of B ). Since leftmost of A is at -a - LA, its distance to hanging point is a + LA (since it's left by a+LA). Similarly, leftmost of B is at b - LB. If b - LB is negative, then that point is left of hanging point, and its distance is -(b - LB) = LB - b. If b - LB is positive, then that point is to the right, so not contributing to left extent. So the left extent Lc is max( a + LA, (LB - b) if LB > b else 0 ). But since a+LA >0, and LB - b might be positive if LB > b, or negative otherwise. So we can take Lc = max( a + LA, max(0, LB - b) ). But is it possible that LB - b > a+LA? Yes, if the B sub-mobile extends left beyond the A sub-mobile's leftmost. That's possible.
But we must also consider that the rod itself may have a left endpoint at -a, but that is covered by a+LA? Actually left endpoint of rod is at -a, and A's leftmost is at -a - LA, so distance from hanging point to leftmost of A is a+LA. The rod itself extends to -a, but that is not further left than A's leftmost if LA≥0. So okay.
Similarly, right extent Rc = max( b + RB, max(0, RA - a?) Actually rightmost of A is at -a + RA. If -a + RA could be positive, then it contributes to right extent: its distance from hanging point is RA - a? Wait coordinate of A's rightmost = -a + RA. If that is positive, then its distance to hanging point is that value. However, -a is negative, RA may be less than a, making -a+RA negative; or greater than a, making it positive. So we need to compute the rightmost point's coordinate and its distance from hanging point if positive. More systematically:
We compute overall leftmost coordinate Lco = min( -a - LA, b - LB ). Since both are negative, the left extent = - Lco. Overall rightmost coordinate Rco = max( -a + RA, b + RB ). Since both are positive, right extent = Rco.
Thus Lc = -min( -a - LA, b - LB ) = max( a + LA, - (b - LB) ) = max( a + LA, LB - b ). But note LB - b could be negative; but then max would be a+LA which is positive. So Lc = max( a + LA, LB - b ) if LB - b > 0 else a+LA. So that's fine.
Rc = max( -a + RA, b + RB ).
Thus we can compute Lc and Rc directly via: Lc = max( a + LA, max(0, LB - b) )? Actually LB - b is positive if LB > b, else negative. But max( a+LA, LB-b ) works because a+LA is always positive, so if LB-b is negative, max yields a+LA.
Similarly, Rc = max( b + RB, max(0, RA - a) )? Because -a+RA could be positive if RA > a; else negative. Since b+RB is always positive, we can compute Rc = max( b + RB, -a + RA if -a+RA > 0 else 0 ). But simpler: Rc = max( b + RB, -a + RA ). Because -a+RA may be negative, but then max picks b+RB. So we can just compute Rc = max( b + RB, -a + RA ). That works because b+RB is positive, so if -a+RA is negative, max is b+RB; if it's positive, we take the larger. So Rc = max( b + RB, -a + RA ). But careful: The coordinate -a+RA might be less than b+RB but still positive; we need the maximum coordinate, so that's correct.
But note: The rightmost coordinate is max(-a+RA, b+RB). That's correct.
Similarly leftmost coordinate is min(-a - LA, b - LB). That is negative; left extent is -min(...). So we can compute Lc = - min( -a - LA, b - LB ) = max( a + LA, -(b - LB) ) = max( a + LA, LB - b ).
Thus Lc = max( a + LA, LB - b ). Since a+LA >=0 and LB - b may be negative; if LB - b negative, Lc = a+LA.
So we have:
Lc = max( a + LA, LB - b ) Rc = max( b + RB, -a + RA )
But check: For leftmost, what about the possibility that b - LB is more negative than -a - LA? That would give LB - b > a+LA? Actually if b - LB is more negative, then - (b - LB) = LB - b is larger than a+LA, so Lc = LB - b. That corresponds to B's leftmost extending beyond A's leftmost. Good.
So those formulas are consistent.
We also need to note that for a leaf, L=0,R=0.
Now we can compute all possible (W, L, R) for each subset of stones (representing which stones are used). Since s <= 6, there are up to 2^6=64 subsets. For each subset, we can store a set of possible (W, L, R) triples (maybe many). But number of possible triples might blow up? Let's estimate: each combination yields a triple with rational numbers? But we can store as doubles with high precision, or better as fractions to avoid floating errors. However, final output is a decimal fraction with tolerance 1e-8. Since weights are integers up to 1000, all computations are rational with denominators that are sums of weights. The widths will be rational numbers with denominators dividing product of sums? But we can compute exactly using fractions (rational numbers) to avoid precision issues. However, we could also compute using double precision, as s small and values limited, error should be manageable if careful. But to be safe, we can use rational numbers as fractions of integers (maybe big integers but sums up to at most 6000? Actually total weight sum ≤ 6*1000 = 6000, but denominators could be products of sums; however, we can represent L and R as rational numbers. They are derived from linear combinations of fractions. Could become complex? Let's try to derive formulas: L and R are recursively defined as max of sums of certain expressions. This involves max operator, which can produce piecewise rational functions. However, the number of possible distinct (L,R) might be limited.
Given s ≤ 6, the total number of distinct full binary trees with labeled leaves (considering ordering) is limited. The number of distinct mobiles (considering assignments of distinct stones) might be at most (2s-3)!! * s! maybe? But actually number of binary tree structures with ordered leaves: number of full binary trees with n labeled leaves and ordered children is (2n-3)!!? For n=6, that is 13579 = 945? Wait (2n-3)!! = (2n-3)(2n-5)...1. For n=6, (26-3)=9, so 97531 = 945. And times permutations of leaves (6! =720) yields 680,400 possibilities. But many will be equivalent if weights equal? But we can still enumerate all recursively using DP over subsets with storing possible triples; each subset of size k can combine from two smaller subsets. The number of possible triples per subset may grow, but with n=6, it's manageable.
Alternatively, we can perform full recursion over all partitions and orderings, generating all possible mobiles and computing width. Since s is only 6, we can do exhaustive search with recursion over the multiset of stones, using memoization to avoid recomputation for same subset (but careful: even with same subset of indices, different orderings inside can yield different (L,R) for same total weight? But total weight is fixed for a given subset, but L,R can vary. So for each subset we need to store all possible (L,R) pairs (or widths directly?) that can be achieved by some mobile using exactly those stones. Then for the full set, we collect all possible widths (L+R) from each (L,R) triple. Then we pick the maximum width < r.
But note: The width of the whole mobile is L+R for the top mobile. However, when we combine mobiles, we use L,R values of sub-mobiles to compute new L,R. So we need to store L,R values, not just width.
Thus DP: For each non-empty subset S of stones (by indices), we compute a set of possible states (W, L, R). W is total weight (sum of weights in S). L and R are non-negative rational numbers (extents). Initially, for singletons {i}: state (wi, 0, 0).
For each subset S with size >=2, we consider all ways to partition S into two non-empty disjoint subsets S1 and S2. But order matters: we need to consider both assignments of S1 as left and S2 as right, and also S2 as left and S1 as right? Actually when we partition S into two unordered subsets, then we consider both orders: (S1 left, S2 right) and (S2 left, S1 right). However, note that if we iterate over all ordered pairs (S1, S2) such that S1 ∪ S2 = S, S1 ∩ S2 = ∅, both non-empty, then we cover both orders. But we should be careful to not double count? It's okay to generate both; the set of states will contain duplicates, but we can store unique states.
Now for each ordered pair (S1, S2), we take each state A from dp[S1] and each state B from dp[S2], and compute new state C as described. Then add C to dp[S].
Complexity: Number of subsets = 2^s ≤ 64. For each subset S, number of partitions into two non-empty subsets: For subset of size k, there are (2^k - 2) / 2 unordered partitions? But we consider ordered pairs, which is number of ways to choose non-empty S1 and S2 with S1∪S2=S, S1∩S2=∅, S1 != ∅, S2 != ∅, and ordered. That count is (2^k - 2) because for each non-empty proper subset S1, S2 = S \ S1 is non-empty. So number of ordered partitions is exactly (2^k - 2). For k up to 6, max is 2^6-2=62. For each such partition, we need to combine states from dp[S1] and dp[S2]. The number of states per subset could be large? Let's bound.
We can compute approximate number of distinct (L,R) values. For each mobile configuration, L and R are determined by the tree and assignments. Since s is small, total number of distinct mobiles is limited. However, DP could produce many states due to combinatorial explosion. Let's estimate: For s=6, total number of distinct ordered trees with labeled leaves (with distinct weights) maybe in thousands. But even if we have up to a few thousand states per subset, DP with 64 subsets * combining might be okay. But we need to be careful about duplicates and performance.
We can store states as pairs of doubles? But we need to compare to r with high precision, and we need to compute maximum width less than r. Since the number of possible widths is limited, we can compute exactly using fractions.
Alternative: Since s ≤ 6, we could directly enumerate all full binary trees (ordered) and all assignments of stones to leaves (permutations) recursively, compute width, and keep track of max < r. That might be simpler to implement without DP, but we must handle duplicate weights efficiently. The number of trees: number of full binary trees with n leaves (ordered) is the Catalan number C_{n-1}. For n=6, C_5 = 42? Actually Catalan numbers: C0=1, C1=1, C2=2, C3=5, C4=14, C5=42. So 42 ordered tree shapes (since ordered trees). Then assign 6 distinct stones (if all distinct) to leaves: 6! = 720. So total 42*720 = 30,240. For each tree, we need to compute width recursively. That's very manageable. But weights may be duplicate; still we can treat stones as distinct indices and then compute, but may generate duplicate width values but that's fine. 30k is tiny. However, we also need to consider that at each internal node, the order of left and right matters, but that is already captured by the ordered tree shape? In an ordered tree, left and right children are ordered. So each shape defines which subtree is left and which is right. So that's enough. But is there any additional degree of freedom? For a given tree shape with leaves assigned, the mobile is fully defined: the rods always hang at the center of gravity. So no other choices.
But careful: The recursive definition of a mobile: either a stone, or a rod with two sub-mobiles at both ends. In the tree representation, each internal node corresponds to a rod, with two children (sub-mobiles). That's exactly an ordered full binary tree. So enumerating all full binary trees with labeled leaves (ordered) yields all possible mobiles.
Thus we can generate all trees via recursion: pick a split of the set of stones into two non-empty subsets, and then recursively build the left and right subtrees. This is exactly the DP approach but we can just do recursion over the multiset of stones (list of weights) and compute width for each tree. Since s ≤ 6, recursion over all partitions (ordered) is fine.
But there is nuance: The order of stones in the list matters? When we partition, we need to consider all ways to assign which stones go to left and which to right. That's essentially generating all ordered trees. The number of ordered full binary trees with labeled leaves (distinct items) is given by the number of ways to parenthesize the sequence with binary operations, which is the number of full binary trees with leaves labeled by the given order? Actually if we consider the stones as distinct and we care about which stone goes where, the number of distinct mobiles (considering stone identities) is the number of full binary trees with labeled leaves times permutations of leaves. But if we generate recursively by picking a subset for left and right, we will count each labeled tree exactly once. Because for a given tree, the set of leaves in left subtree is a specific subset, and then recursively. So that enumeration yields all distinct trees (with labeled leaves). So we can simply do a recursive function that given a list of indices (or multiset of weights) returns a set of possible (L,R,W) triples? Actually we want width for the top. But we can compute the width directly from the tree built. Since we are enumerating all trees, we can compute the width for each and keep track of max < r.
But careful: The width depends on L and R values for subtrees. So during recursion, we need to compute for each subtree its total weight and its left/right extents (L,R). So we can write a recursive function that given a multiset of stones (list of weights), returns all possible (W, L, R) triples achievable by some mobile using exactly those stones. This is essentially DP over subsets but with recursion and caching based on the multiset. Since stones may have duplicate weights, using a sorted tuple as key to memoize can reduce duplicates. For s=6, the number of distinct multisets is limited (partitions of 6 with weights up to 1000, but many combos). However, we can simply treat indices and use bitmask DP to avoid duplication due to weight symmetry? But if weights are equal, different subsets of same size and same weight multiset may produce same (W,L,R) possibilities, but we can still compute DP over subsets (bitmask) without caring about duplicates because the number of subsets is small (64). Even if weights are equal, dp[mask] will store states based on which stones are in the mask, but if stones have same weight, dp[mask1] and dp[mask2] with same total weight and same set of weights (but different indices) might produce same states. That's okay; we will compute them separately but still number small.
Given s ≤ 6, we can implement DP over bitmask. Let n = s. We'll assign indices 0..n-1. For each mask (1..2^n-1), we compute a list of (W, L, R) states. Initially for masks with one bit, state (w[i], 0, 0). For larger masks, we iterate over proper non-empty submask sub of mask (with sub !=0 and sub != mask). But we need ordered pairs: for each such sub (as left), the complement as right (provided complement not empty). However, this will consider both (sub, rest) and (rest, sub) when we iterate over all sub? Actually if we iterate over all non-empty proper submasks sub, then each unordered partition appears twice (once with sub as left, once with rest as left) unless sub == rest (impossible unless mask size even? But when mask size is even and sub equals rest? That would require sub = mask ^ sub => sub = mask/2 in bits, but still they are distinct as sets if sub != rest? Actually if sub == rest then mask = sub ∪ rest = sub ∪ sub = sub, so sub = mask, impossible because sub proper. So they are distinct. So iterating over all sub will generate both orders.