DMOPC '15 Contest 3 P2 - Cheesecake Distribution

View as PDF

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

FatalEagle has managed to survive his first semester English course so far. To celebrate, he invited 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 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 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 , the number of friends.

The next line will contain space-separated nonnegative integers, the number of slices that each friend grabbed. Each friend will have no more than 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

3

Explanation for Sample Output 1

FatalEagle will perform the following steps:

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

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

7

• commented on April 4, 2018, 7: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

• commented on Aug. 7, 2017, 5: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?

• commented on Aug. 7, 2017, 7:02 p.m.

Each friend can already have the same amount of slices.

• commented on May 14, 2017, 10:43 a.m.

if it is impossible then cant FatalEagle split a slice into halves?

• commented on March 18, 2016, 1:31 p.m.

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

• commented on March 19, 2016, 6: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.

• commented on Dec. 27, 2015, 11:21 a.m. edited

Edit: actually, all judges are dead

• commented on Dec. 15, 2015, 5:24 p.m.

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

uh, FatalEagle, are you communist?

• commented on Dec. 15, 2015, 6: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!

• commented on Dec. 8, 2015, 12:10 p.m. edited

Nevermind.