The Quarrymaster's Carts
# The Quarrymaster's Carts
The quarry above bitwick cuts its blocks at dawn and lays them out along the loading dock in one long row. At dusk the carts come down the road and are loaded strictly in order: the first cart takes a run of blocks from the front of the row, the next cart takes the run that follows it, and so on until the row is empty. A cart may not skip a block, the row is never reordered, and no cart goes back up the hill empty.
The quarrymaster wants the heaviest cart of the evening to be as light as it can be, because the road washes out under a heavy axle.
You are given:
weights— a non-empty list of positive integers, the blocks in dock order.carts— an integer with1 <= carts <= len(weights).
A loading assigns each of the carts carts one contiguous, non-empty run of blocks, the runs in order covering every block exactly once. A cart's load is the sum of the blocks in its run.
Return, as an integer, the smallest possible load of the heaviest cart over all such loadings.
examples
- case 1
weights of [7, 2, 5, 10, 8], carts of 218 — the runs [7, 2, 5] and [10, 8] weigh 14 and 18; every other split has a heavier cart - case 2
weights of [1, 4, 4], carts of 34 — each cart takes one block, and the heaviest block is 4 - case 3
weights of [2, 3, 1, 4], carts of 110 — the single cart must take the whole row
- reward
- 350 XP
- signature
heaviestLoad
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- two carts over five blocks
- one cart per block
- a single cart takes the row
- a lone block
- balanced halves
- awkward remainder in three
- one boulder among pebbles
- the long dock run