Kata

Description

There are some candies which need to be distributed to some children as fairly as possible. Your assignment is to implement a function with signature distribute(m, xs) while m represents candies' amount and xs contains some weights which represents each child's weight to gain the candy. The function should return a List which holds the candies' amount each child should gains.

Rule

• Each child hold a weight which represents his deserved shares of the candies.

• If children with share receiving weight == 0 don't deserve candies at all.

• Each share is a integer, and may be different from each other, so you should guarantee that the variance of share to be as small as possible.

• For fairness, we prescribe that less weight, higher priority to gain shares.

• For fairness, if there are same weights for different children, we prescribe that from left to right in xs, priority is getting lower and lower to gain shares.

Example & Explanation

distribute(50, [6, 4, 3, 0, 5, 2, 3]) should be [12, 8, 8, 0, 10, 6, 6]

Proof:

∵ sum([6, 4, 3, 0, 5, 2, 3]) = 23 and divmod(50, 23) = (2, 4) 
∴ Each share can be 2 or (2 + 1 = 3) candies.

count(candies = 3) = 4 & count(candies = 2) = 23

The child with lower weight has higher priority to choose share, so...
The child with weight = 0 can be ignored.
The child with weight = 2 get 2 * 3 = 6 candies.

The child located at left has higher priority to choose share, so...
The 1st child with weight = 3 get 2 * 3 + 1 * 2 = 8 candies. 4 shares with candies = 3 have been distbuted.
The 2nd child with weight = 3 get 3 * 2 = 6 candies.
and so on......

ps: Is it seems to be very confusing?

Notice

• m < 0 is equivalent to m = 0
• if sum(xs) = 0 the algorithm should return [0] * size(xs)

Input

1. m: Integer 「 m ≤ 10 ^ 6」 represents the candies' total amount.
2. xs: [x: Integer] 「 x ≥ 0 & size(xs) ≤ 10 ^ 3 」 represents the weight each child holds.

Output

[Integer]