Problem Statement |
| | Mr. Green owns a beautiful park full of trees. Recently, he arranged a new lane in the park and planted N trees along the lane.
The trees are numbered from 0 to N-1 in the order that they occur along the lane. It is known that once the i-th tree
grows up, its height in meters will be a random integer uniformly distributed between low[i] and high[i],
inclusive.
Mr. Green has quite a strange conception about beauty. In particular, he is very fond of so called alternating sequences of
integers, which are defined by the following rules:
- Every sequence of 1 integer is alternating.
- A sequence of 2 integers (A, B) is alternating if and only if A is not equal to B.
- A sequence of 3 integers (A, B, C) is alternating if and only if (A < B and B > C) or (A > B and B < C).
- A sequence of L, L > 3, integers (A[0], A[1], ..., A[L-1]) is alternating if and only if each triple of consecutive integers
in the sequence form an alternating sequence. In other words, each of the sequences (A[0], A[1], A[2]), (A[1], A[2], A[3]), ...,
(A[L-3], A[L-2], A[L-1]) must be alternating.
Mr. Green measures the beauty of an alternating sequence as the sum of absolute differences between all pairs of its consecutive elements.
In other words, for a sequence (A[0], A[1], ..., A[L-1]), its beauty is equal to |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[L-2] - A[L-1]|.
Note that the beauty of a sequence consisting of 1 element is equal to 0.
Once all the trees grow up, Mr. Green will write down their heights in the order that they occur along the lane. If the resulted sequence of integers
is alternating, then he will be satisfied with the resulting lane. Otherwise, he will cut some trees down
so that the sequence formed by the remaining trees is alternating. If there are several ways to obtain an alternating sequence, he will choose a way among them that results in a sequence with maximum possible beauty.
Return the expected value of the beauty of the resulting sequence.
|
| |
Definition |
| | | Class: | AlternatingLane | | Method: | expectedBeauty | | Parameters: | int[], int[] | | Returns: | double | | Method signature: | double expectedBeauty(int[] low, int[] high) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The returned value must have an absolute or relative error less than 1e-9. |
| |
Constraints |
| - | low will contain between 1 and 50 elements, inclusive. |
| - | high will contain the same number of elements as low. |
| - | Each element of low and high will be between 1 and 100,000, inclusive. |
| - | For each valid index i, low[i] will be less than or equal to high[i]. |
| |
Examples |
| 0) | |
| | | Returns: 0.0 | | Here we have only 1 tree, so the beauty of the resulting sequence will be 0.
|
|
|
| 1) | |
| | | Returns: 1.0 | | Once all the trees grow up, 8 different lanes are possible with equal probability. In cases (1, 1, 1) and (2, 2, 2), Mr. Green will cut 2 trees and the beauty will be 0. In cases (1, 1, 2), (2, 2, 1), (1, 2, 2), (2, 1, 1), he will cut the middle tree and the beauty will be 1. Finally, in cases (1, 2, 1) and (2, 1, 2), he won't cut any trees and the beauty will be 2. Therefore, the answer is (4/8) * 1 + (2/8) * 2 = 1. |
|
|
| 2) | |
| | {1, 3, 5, 7, 9} | {2, 4, 6, 8, 10} |
| Returns: 8.0 | | Here, Mr. Green will always leave only the first and the last trees. |
|
|
| 3) | |
| | {4, 3, 3, 7} | {10, 7, 7, 7} |
| Returns: 6.171428571428572 | |
|