Kiana likes desserts. One day, she bought
Since each slice of cake has a different flavour, Kiana and TinyTree wants to cut each slice into two pieces, each of then taking one piece to taste. However, slicing cakes fairly is an age-old problem. After some negotiation, it was decided Kiana would slice the cakes with her knife, and TinyTree would get
Step 1: Kiana chooses a slice of cake which has not been cut, and cuts it into two pieces. The sizes of the resulting pieces are decided by Kiana, and can be any two nonnegative real numbers summing up to the size of the original slice.
Step 2: After TinyTree observes the sizes of the two cake pieces sliced by Kiana, if she has any 'cake selection rights' remaining she can choose whether or not to consume one such right.
Step 3: If TinyTree exercises 'cake selection rights', she can select one of the two cake pieces for herself, and the other will go to Kiana. Otherwise, Kiana selects one of the two cake pieces for herself, and the other goes to TinyTree. This process then repeats from Step 1 until all slices of cake have been eaten.
Kiana and TinyTree both want to maximise the sum of sizes of cake they receive, and will slice and select optimally to achieve this. What is the sum of sizes of cake that Kiana will obtain?
The first line of input consists of two integers
The second line of input consists of
Output a single real number, the sum of slices of cake Kiana will obtain, in decimal notation and with relative error no more than
Subtask # | Score | Constraints |
---|---|---|
1 | 8 | |
2 | 28 | |
3 | 64 | No additional constraints |
Sample Input 1 | Sample Output 1 |
4 3
|
5.250000
|
In this input example, there are 4 slices of cake and TinyTree has 3 opportunities to exercise 'cake selection rights'. One optimal solution is:
Round 1: Kiana chooses the slice with size 3, and cuts it into pieces with sizes 1.75 and 1.25. TinyTree exercises 'cake selection rights' and takes the piece with size 1.75. Kiana receives the piece with size 1.25.
Round 2: Kiana chooses the slice with size 1, and cuts it into pieces with sizes 0 and 1. TinyTree does not exercises 'cake selection rights'. Kiana takes the piece with size 1.
Round 3: Kiana chooses the slice with size 2, and cuts it into pieces with sizes 1 and 1. TinyTree exercises 'cake selection rights'. Both TinyTree and Kiana recieve a piece with size 1.
Round 4: Kiana chooses the slice with size 4, and cuts it into pieces with sizes 2 and 2. TinyTree exercises 'cake selection rights'. Both TinyTree and Kiana recieve a piece with size 2.
It can be proven that no other strategy will allow Kiana or TinyTree to get more cake if the other of them responds optimally.
Subtask | Score |
---|---|
1 | 8 |
2 | 28 |
3 | 64 |