DMOPC '15 Contest 3 P2 - Cheesecake Distribution - Olympiads Online Judge

DMOPC '15 Contest 3 P2 - Cheesecake Distribution

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

FatalEagle has managed to survive his first semester English course so far. To celebrate, he invited $N$ ~N~ friends over for a party!

For dessert, he decided to cut ~~cheesecake~~ some cheesecake. FatalEagle's friends are greedy. As soon as he finished, his friends grabbed all the slices that they could. FatalEagle is a strong proponent of equality, so he would like to redistribute the slices such that each friend gets the same amount. He will do this by persuading a friend with the maximum number of slices to give $1$ ~1~ slice to a friend with the minimum number of slices, and repeating this process until the slices are equally distributed. Since FatalEagle's friends are also stubborn, so it will take him $1$ ~1~ minute to convince them each time.

FatalEagle wants to know how long it will take for him to evenly distribute the cheesecake slices.

Input Specification

The first line of input will contain $N$ ~N~ $(1 \le N \le 10^5)$ ~(1 \le N \le 10^5)~, the number of friends.

The next line will contain $N$ ~N~ space-separated nonnegative integers, the number of slices that each friend grabbed. Each friend will have no more than $10^{12}$ ~10^{12}~ slices. (It's a really big cheesecake)

Output Specification

Output one integer, the number of minutes it will take for FatalEagle to evenly distribute the cheesecake following this process. If this is not possible, output Impossible.

Note

The input and output may not fit in 32-bit integer variables. Please use 64-bit integer variables (such as long in Java and long long in C/C++).

Sample Input 1

3
6 1 2

Sample Output 1

Explanation for Sample Output 1

FatalEagle will perform the following steps:

Ask friend $1$ ~1~ to give a slice to friend $2$ ~2~.
Ask friend $1$ ~1~ to give a slice to friend $3$ ~3~.
Ask friend $1$ ~1~ to give a slice to friend $2$ ~2~.

Sample Input 2

2
1 2

Sample Output 2

Impossible

Explanation for Sample Output 2

No matter what FatalEagle does, one friend will always have more than the other.

Sample Input 3

10
3 5 4 6 5 2 4 6 9 6

Sample Output 3

Comments

1

raytonlin1 commented on April 4, 2018, 11:15 p.m. ← edited →

IDK what's wrong with my C++ 14 code, it keeps saying Batch 5 testcase 1 is WA. I have an output of Impossible.

EDIT: NVM I put long long int instead of long long

1

fishingguy456 commented on Aug. 7, 2017, 9:24 p.m.

I tried my code with all the test cases and my own case, but it still says that batch 4 has the wrong answer. What is wrong with my code?

1

TheZombieCloud commented on Aug. 7, 2017, 11:02 p.m.

Each friend can already have the same amount of slices.

-4

splacorn commented on March 18, 2016, 5:31 p.m.

Hmmmm when I'm testing my code it works. but when I submit it, it says it's incorrect.....

2

moladan123 commented on March 19, 2016, 10:17 p.m.

Your code has a tiny little mistake in it. Just remember to be careful with indentation in python and you will find it.

12

poinzetta commented on Dec. 15, 2015, 10:24 p.m.

FatalEagle is a strong proponent of equality, so he....

uh, FatalEagle, are you communist?

9

Xyene commented on Dec. 15, 2015, 11:17 p.m.

In his defense, the problem statement does say,

As soon as he finished, his friends grabbed all the slices that they could.

We're led to believe that there are not many slices left, since FatalEagle was there first!