Sink.
You are setting up the hydration station at a gym. As you finish up, you notice that there is a dial to tweak how much water the station dispenses each time the button is pressed. This dial can be set to dispense any positive real number of millilitres.
Since you pay the water bills, the question is how to set the dial to waste as little water as possible.
When someone wants water, they walk up to the station with their empty bottle and press the button. Initial inaccuracy makes them spill the first $$$1$$$ millilitre of each press; the rest goes into the bottle. They keep pressing as long as the bottle is not yet full. On the last press, whatever water no longer fits into the bottle is wasted too.
Say the station is set to dispense $$$90$$$ millilitres of water per press, and someone with a $$$400$$$ millilitre bottle uses it. They press four times, each time wasting $$$1$$$ millilitre due to moving around. At that point they have $$$356$$$ millilitres in their bottle, so they press one more time. The first millilitre of that portion gets wasted, the next $$$44$$$ go into the bottle, and the last $$$45$$$ are superfluous and are wasted as well. Thus a total of $$$50$$$ millilitres are wasted.
With some rather dubious methods you have collected the data on what size water bottle every regular client uses. Each bottle gets filled, starting from empty, exactly once per day.
How many millilitres of water should the station dispense per button press to waste as little water as possible?
The input consists of:
- One line with an integer $$$n$$$ ($$$1 \leq n \leq 100\,000$$$), the number of bottles.
- One line with $$$n$$$ integers $$$b_1, \dots, b_n$$$ ($$$1 \leq b_i \leq 100\,000$$$), the sizes of the bottles in millilitres.
Output the number of millilitres each press of the button should dispense to minimise waste. There is always an optimal amount that is rational; output any one of them as a reduced fraction of the form p/q.
3100 150 200
51/1
337 72 99
107/8
101 2 3 4 5 1 2 3 4 5
3/1
