Energy Drink
InterviewTime limit1sMemory limit256 MB
Combine N drink amounts two at a time, where pouring one into another keeps half the poured amount, and maximize the final total.
- Level
Medium5 of 10
- Topics
- Greedy, Sorting, Math, Implementation
- Solved
- No attempts yet
Problem
Fain is an office worker who likes energy drinks. An energy drink contains ingredients such as caffeine, arginine, taurine, and niacin, and it is a supplement beverage that helps with fatigue recovery.
After finishing overtime work, Fain leaves the office at midnight, and it is already 1 a.m. The weekend is still far away, and Fain has to be at work on time the next day as well, so today he reaches for an energy drink again.
Exhausted from repeated overtime, Fain needs more energy and fatigue recovery than usual. He decides to combine the energy drinks he has at home into a single energy drink and drink it all at once.
Fain combines the energy drinks as follows.
- Pick any two different energy drinks.
- Pour one energy drink entirely into the other. However, Fain's hands shake from the aftereffects of overtime, so during pouring he spills half of the original amount onto the floor.
- Throw away the empty energy drink left after pouring.
- Repeat steps 1 to 3 until only one energy drink remains.
For example, suppose there are two energy drinks a and b with amounts xa and xb. He can choose one of the following.
- Make the amount of a equal to xa + (xb / 2) and throw away b
- Make the amount of b equal to xb + (xa / 2) and throw away a
Fain wants to maximize the amount of the combined energy drink. Help poor Fain!
Input
The first line gives the number of energy drinks Fain has, N. (2 ≤ N ≤ 105)
The second line gives the amount of each energy drink, separated by spaces. The i-th integer xi (1 ≤ xi ≤ 109) means the amount of energy drink i is xi.
Output
On the first line, print the maximum amount of energy drink Fain can make.
An absolute or relative error of up to 10-5 is allowed.