TLE '17 Contest 4 P6 - Fax's Christmas Bash

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types
Fax and his wingmate Flaco enjoying the party.

Fax McClad, Croneria's most festive bounty hunter, is hosting a big Christmas party in his neighbourhood! His neighbourhood can be thought of as a straight line.

Fax has N crew members he can invite. The i^\text{th} crew member is located x_i metres to the east of the origin. He would like to invite some of his crew members to attend his party, but he wants to minimize the amount of time wasted. In particular, if the party is located y metres to the east of the origin, then the i^\text{th} crew member will waste |x_i-y|^3 time by going to the party.

Fax wants to invite all of his crew members to the party, but the total amount of time wasted might become too large. For each party size k, what is the best location to host the party if Fax only invites the first k crew members? In other words, what is the value of y that minimizes:

\displaystyle |x_1-y|^3 + |x_2-y|^3 + \dots + |x_k-y|^3

Note: y can be a real number.


1 \le N \le 300\,000

The absolute value of any coordinate will not exceed 15\,000. That is, |x_i| \le 15\,000.

Subtask Points Additional Constraints
1 10 0 \le x_i \le 1 for all 1 \le i \le N
2 10 N \le 30
3 20 N \le 900
4 60 No additional constraints.

Input Specification

The first line will contain the integer N.

On the next N lines, the i^\text{th} line will contain the integer x_i.

Output Specification

There will be N lines of output. The k^\text{th} line of output will contain the best location to host the party if the first k of Fax's crew members are invited.

Your output will be judged as correct if the absolute error does not exceed 10^{-3}.

Sample Input


Sample Output



  • 4
    Beautiful_Times  commented on Jan. 17, 2018, 2:59 a.m.

    Is an editorial ever going to be released for this problem?