An Animal Contest 2 P2 - Koala Party

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Java 2.0s
Python 2.0s
Memory limit: 256M
Java 512M
Python 512M

Authors:
Problem type

At his birthday party, Sanjay the Koala wants to prepare a bowl of cookies for each of his N friends, filling N bowls with bags of Oreos. He realizes, however, that each Oreo bag has a different number of cookies, with the i^{th} bag having a_i cookies. Sanjay wants everyone to have the same number of cookies, but as his friends are calling him back, he only has time to take a number of cookies from a single bowl and place all of the cookies he took into another bowl. Given this constraint, Sanjay wants to know the maximum number of bowls he can have with an identical number of cookies! Can you help him?

For this problem, Python users are recommended to use PYPY over CPython.

Constraints

For all subtasks:

2 \le N \le 4 \cdot 10^3

1 \le a_i \le 10^9

All a_i are distinct.

Subtask 1 [20%]

2 \le N \le 200

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line of input will contain the integer N.

The second line of input will contain N space-separated integers a_i.

Output Specification

Output the maximum number of bowls with an identical number of cookies that Sanjay can obtain.

Sample Input 1

3
3 1 5

Sample Output 1

3

Explanation for Sample 1

We move 2 cookies from the third bowl into the second, resulting in 3 cookies in all three bowls.

Sample Input 2

4
1 2 6 5

Sample Output 2

2

Comments

There are no comments at the moment.