You have an army of size $n$ that you need to split up to fight $k$ battles simultaneously against an opposing army $A$. In each battle, the army with the most troops present wins - no one wins a tie. Your scouts have just reported back with the enemy troops' movements - how can you divide your army to win the most battles? What's more, if 2 different arrangements win the same number of battles, you prefer the arrangement that beats the most enemy soldiers.

Input

The integers $n, k$ and an array $A$ that contains the number of enemy troops at each battle location.

Output

An array corresponding to A that represents the number of your own troops you will send to that location. There are most likely be multiple solutions - you may return any possible solution that maximizes the amount of battles won while also maximizing the numbers of soldiers beaten within the maximum amount of battles won.

Example

$n = 100, k = 5, A = [20, 20, 20, 20, 20]$

The enemy has split their army evenly - to win the maximum amount of battles, 4, we can simply ignore battle 1 and distribute evenly among the other 4, for example $[0, 25, 25, 25, 25]$.

$n = 50, k = 5, A = [40, 30, 20, 10, 0]$

We're outnumbered, but we can still win 3 battles. $[0, 0, 25, 15, 10]$ would win 3 battles, but remember, we want to win against larger enemy forces if possible, so a correct optimal answer could be $[0, 35, 0, 14, 1]$

More Input/Output Examples

Only one of many possible outputs is shown.

n, k, A -> Output
1, 1, [0] -> [1]
2, 2, [1,1] -> [2, 0]
10, 3, [4, 3, 3] -> [5, 0, 5]
100, 3, [50, 25, 25] -> [60, 40, 0]
100, 5, [33, 34, 33, 0, 0] -> [0, 50, 40, 5, 5]

This is code-golf, so shortest solution in each language wins.

posted almost 4 years ago

CC BY-SA 4.0

3y ago by General Sebast1an‭

Quintec‭

2316 reputation 17 46 243 49