[email protected] High School Programming Competition 2019

Start

2019-04-13 08:00 AKDT

[email protected] High School Programming Competition 2019

End

2019-04-13 12:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1133 days 16:14:49

Time elapsed

4:30:00

Time remaining

0:00:00

Problem J
Rent Division

In an apartment just down the street from Colorado School of Mines, there are $N$ roommates who are trying to figure out how to pay their rent every month. These roommates also have other expenses that they share as well. Rather than using Venmo to share those expenses like sane individuals, they have decided to handle all money exchanges by paying different proportions of rent at the beginning of each month.

For example, let’s say there are $N = 4$ roommates in an apartment: Jack, Joseph, Jordan, and David. Jack always pays the Internet and utility bills, totalling $\$ 81$ ($c_1$), while everyone else pays nothing ($c_2 = c_3 = c_4 = \$ 0$). Assuming rent this month is $\$ 1963$ ($R$), how much should each person pay (rounded up), so that each of their total contributions (including expenses that they have already paid) are equal and so that the entire rent is paid?

These roommates are entirely stumped because this is such a difficult calculation. Your mission, if you choose to accept it, is to aid these $N$ roommates in finding out what portion of the rent they need to pay individually. If it is not possible, then you should output “not possible”, and everyone has to get Venmo. This happens if someone pays too much in other expenses and would need to be paid, rather than pay, rent.

Input

The first line consists of one integer, $N$ ($1 \leq N \leq 100\, 000$) which is the number of roommates. The next $N$ lines each have one integer $c_ i$ ($0 \leq c_ i \leq 10\, 000$) indicating how much person $i$ has paid on non-rent expenses.

The last line is the rent due this month, $R$ ($0 \leq R \leq 500\, 000\, 000$).

Output

If it is not possible for the total contributions from each roommate to be equal, then output a single line with the words “not possible”.

If it is possible for each of the $N$ roommates to make an equal total contribution, then output $N$ lines each with an integer, $p_ i$, indicating how much of the rent the corresponding person, person $i$, should pay.

Sample Input 1 Sample Output 1
4
81
0
0
0
1963
430
511
511
511
Sample Input 2 Sample Output 2
1
0
1
1
Sample Input 3 Sample Output 3
5
1000
0
0
0
0
100
not possible