\(5^{th}\) round, March \(17^{th}\), 2012

N rectangles with given masses (m_{i}) and equal lengths (2) and heights (h) are arranged in a Cartesian
plane such that:

rectangle edges are parallel to the coordinate axes;

the \(y-co\)ordinates of lower horizontal edges are distinct and assume the following values: 0, h,
2h, 3h, ..., (\(N - 1\))h;

the lowest rectangle‟s lower left corner has coordinates (-2, 0), while the lower right corner
coincides with the origin.

The \(X-ce\)ntre of a rectangle is the \(x-co\)ordinate of the midpoint of its lower edge.
The \(X-ba\)rycentre of one or more rectangles is the weighted average of their \(X-ce\)ntres. It is computed
as




\(i\)
\(i\)
\(i\)
\(i\)
\(m\)
\(i\)
Xcentre
\(m\)
\(e\)
Xbarycentr
)
(

In other words, the mass of each rectangle is multiplied by its \(X-ce\)ntre and the sum of these products
is then divided by the total mass of the rectangles.
An arrangement is stable if, for each rectangle A:

the \(X-ba\)rycentre of rectangles above A has distance of at most 1 from the \(X-ce\)ntre of A (i.e. is
contained in the \(x-in\)terval that covers A).
Intuitively, stability of an arrangement can be understood as the precondition for the arrangement to
not fall apart. The arrangement in the figure on the left is unstable since the \(X-ba\)rycentre of the top
two rectangles falls outside the rectangle underneath (the distance of the \(X-ba\)rycentre to the \(X-ce\)ntre
of the underlying rectangle is greater than 1). The arrangement in the figure on the right is stable.
Given the masses of all rectangles, find the largest (“rightmost”) possible \(x-co\)ordinate of any
rectangle corner in a stable arrangement. You are not allowed to change the order of rectangles (they
are given from the lowest to the highest one).

In test cases worth 30% of points, the rectangles will be ordered from the heaviest to the lightest one.

The first line of input contains the positive integer N (\(2 \le N \le 300\,000\)), the number of rectangles.
Each of the next N lines contains a single positive integer less than 10 000, the mass of a rectangle. The
masses are given in order from the lowest to the highest rectangle.

\(5^{th}\) round, March \(17^{th}\), 2012

The first and only line of output must contain the required rightmost \(x-co\)ordinate. The given result
must be within 0.000001 of the official solution.

생성자가 기록되지 않았습니다.

출처 COCI 2011/2012 Contest 5