## Monkey Country

View as PDF

Points: 10
Time limit: 3.0s
Memory limit: 512M

Author:
Problem type

Victor lives in a monkey country where every day, out of the monkeys who have money, the top of monkeys earn one dollar while everyone else loses one dollar. When a monkey runs out of money, he goes bankrupt and loses his citizenship too is no longer one of the monkeys with money. At first, there are monkeys and the monkey has dollars. Each monkey has a distinct number of dollars to begin with. Victor would like to know how many days there are until each monkey runs out of money.

#### Input Specification

The first line contains integers , , and (, ), the number of monkeys in the country and the special numbers and .

The next line will have a list of integers, (), the of which is how many dollars the monkey has. No two monkeys have the same amount of money ( if ). The amount of money of the monkeys are sorted in increasing order.

#### Output Specification

In one line, print integers, the of which is how many days there are until the monkey runs out of money modulo .

#### Sample Input 1

5 1 2
1 2 3 4 5

#### Sample Output 1

1 2 3 8 21

#### Sample Input 2

2 1 2
999999999 1000000000

#### Sample Output 2

999999999 999999984

#### Explanation for Sample 1

At the start, the money count is 1 2 3 4 5.

On day 1, the top monkeys gain money, and everyone else loses money. Thus, the new money count becomes 0 1 2 5 6. Here, monkey 1 goes bankrupt on day 1.

The rest of the days are:

0 0 1 6 7 monkey 2 goes bankrupt on day 2.

0 0 0 5 8 monkey 3 goes bankrupt on day 3.

0 0 0 4 9

0 0 0 3 10

0 0 0 2 11

0 0 0 1 12

0 0 0 0 13 monkey 4 goes bankrupt on day 8.

0 0 0 0 12

...

0 0 0 0 1

0 0 0 0 0 The monkey game finally ends when monkey 5 goes bankrupt on day 21.

• commented on Jan. 11, 2021, 7:42 p.m. edited

Is this problem impossible to do with python 3 due to lack of time?

• commented on Jan. 11, 2021, 9:43 p.m.

Yes, due to the testers having a lack of time, this problem is not solvable in Python 3.

In all seriousness, there is currently an AC using PyPy2. Perhaps PyPy3 will pass?

• commented on Jan. 11, 2021, 10:14 p.m. edited

Okay, thanks for the clarification!

• commented on Jan. 11, 2021, 10:05 p.m. edit 2

due to the testers having a lack of time

no u

• commented on Jan. 11, 2021, 5:31 p.m.

Try to avoid using doubles and the floor or ceil function for this problem.

• commented on Jan. 11, 2021, 10:35 p.m.

Including floor division?

• commented on Jan. 12, 2021, 6:37 p.m.

Integer division is fine, I think issues only arise when a sub answer to an operation is stored as a double and then the floor function is used. For example storing P divided by Q as a double and then multiplying by K and flooring this value caused an error in my code. Doing by K * P and then integer division to divide by Q will not result in errors.