TLE '16 Contest 1 P2 - Heavy-Light Decomposition

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 128M

Author:

Problem type

Fax McClad, Croneria's strongest bounty hunter, needs to move $N$ ~N~ $(1 \le N \le 1\,000)$ ~(1 \le N \le 1\,000)~ heavy boxes into his Kyuwing, his personal spacecraft. The $i^\text{th}$ ~i^\text{th}~ box has a weight of $w_i$ ~w_i~ $(1 \le w_i \le 100\,000)$ ~(1 \le w_i \le 100\,000)~.

Fax is strong enough to carry the boxes alone, but he is lazy and he wants his wingmate Flaco to help. Flaco is also lazy and will only carry boxes that are considered to be "light." However, the concept of "light" must be fair to both Fax and Flaco. They decide that a "light" box is a box with a weight less than or equal to the average weight of all boxes. All other boxes are "heavy."

Flaco notices a catch with this definition of "light". The average is not clearly defined, so he is allowed to determine which average (arithmetic mean, mode, or median) they should use. In the case that there is more than one value that occurs most frequently, the mode is the arithmetic mean of all such values.

Help Flaco to determine the minimum number of boxes he will carry if he optimally chooses which average to use.

Input Specification

The first line will contain a single integer, $N$ ~N~, the number of boxes.

$N$ ~N~ lines of input follow. The $i^\text{th}$ ~i^\text{th}~ line will contain a single integer, $w_i$ ~w_i~.

Output Specification

Output a single integer, the minimum number of boxes Flaco will carry if he optimally chooses which average to use.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Comments

1

therealwill commented on Sept. 21, 2016, 9:31 p.m.

is the mean rounded

1

ZQFMGB12 commented on Sept. 21, 2016, 9:40 p.m.

"They decide that a "light" box is a box with a weight less than or equal to the average weight of all boxes"