# Win a War (or at least a few battles)

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.

## 2 answers

#
BQN, 44 bytes^{SBCS}

```
+´{(≠↑𝕨-𝔽)⊸+2↓⊑∨(≍×𝕨≥⊢)○𝔽˜⟜×⊸∾¨(<1+𝕩)×⥊↕2¨𝕩}
```

The solution is a function that takes *n* as the left argument (`𝕨`

) and *A* as the right argument (`𝕩`

). *k* is just the length of *A*, so it's not used as an argument. The function builds a list of all possible combinations, then calculates a score for each one: the number of battles won followed by the number of troops required, but reduced to 0 if it requires more troops than are available. It gives a wrong answer if no battles can be won since all scores are 0 (could be fixed by incrementing the not-impossible scores). Note that the number of troops required is always one more than the number of enemy troops.

Range (`↕`

) makes the list of combinations. When given a shape argument, it returns an array of that shape where each element's value is its own index. With a list of 2s, the possible indices for each axis are 0 and 1, and the result contains every combination of choices. But it's an array, so Deshape (`⥊`

) is needed to turn it into a list that can be sorted.

Combinators and trains are used several times.

The function consists of a block 1-modifier (inside `{}`

) applied to the operand `+´`

(Plus Fold, that is, sum) to give a derived function. Inside the modifier `𝔽`

is the operand (sum) `𝕨`

is the left argument *A*, and `𝕩`

is the right argument *n*. Explanation for the three sections:

```
(<1+𝕩)×⥊↕2¨𝕩 # Create list of combinations
2¨𝕩 # List with each element of 𝕩 replaced with 2
↕ # Range: array of index lists with that shape
⥊ # Flatten from 2×2×2… array to list
(<1+𝕩) # Enclose 1+𝕩, giving a 0-axis array
× # Multiply: turn 1s in ⥊↕2¨𝕩 into entries of 1+𝕩
2↓⊑∨(≍×𝕨≥⊢)○𝔽˜⟜×⊸∾¨ # Select the best list
¨ # On each list:
⟜× # Use sign (1 if some, 0 if none) as right argument
˜ # No wait, left argument
○𝔽 # Sum both arguments (values and signs)
≍ # Pair sums: ⟨battles won, troops required⟩
𝕨≥⊢ # Do we have the troops? ⊢ is right argument
( × ) # Multiply: set score list to 0 if impossible
⊸∾ # Prepend to original list
∨ # Sort descending
⊑ # First—highest—entry
2↓ # Remove score, leaving required troop counts
(≠↑𝕨-𝔽)⊸+ # Add in remaining troops
𝕨-𝔽 # Troops left over
≠ # Length of result list
( ↑ ) # Take, padding leftovers with 0
⊸+ # And add to troop counts
```

#### 0 comments

# JavaScript, 227 bytes

```
(n,k,A,C=(a,b)=>a?[...C(--a,b),b(a)]:[],f=m=>m?C(n+1,i=>f(m-1).map(([p,s])=>
[[...p,i],s+i])).flat():[[[],0]])=>f(k).map(([b,s])=>a=s-n?a:b.map((a,b)=>(q
=A[b])<a&&(e++,f+=q),e=f=0,[,c,d]=a)&&e<c|e==c&f<d?a:[b,e,f],a=[,-1])&&a[0]
```

Explanation: recursively generates all possible troop arrangements of length $k$ whose sum is $n$ and picks the one with the maximum score.

Try it online! (229 bytes, because TIO uses an old version of Node.js that has a parsing issue when an arrow function appears inside a call)

## 2 comments

Will there ever be an input where no battle can be won? For example

`10, 3, [50, 60, 70]`

? — DJMcMayhem 3 months ago@DJMcMayhem hm, I didn't think of it, so I'm going to say no now — Quintec 3 months ago