The Quarry Carts of Bitwick
The quarry above bitwick cuts stone blocks and lays them in a single row down the haul road, in the order they were cut. At dawn the carts roll up and are loaded from the near end of the row to the far end, and the carter is paid by the weight of whichever cart ends up heaviest.
blocks is a list of positive integers: the weight of each block, in road order. carts is a positive integer, at least 1 and at most the length of blocks. blocks has at least one element.
Every block must be loaded, each into exactly one cart. Each cart takes a contiguous run of blocks from the row, every cart takes at least one block, and the runs are taken in order along the row — so a loading is a division of the row into exactly carts consecutive non-empty pieces. A cart's load is the sum of the weights of the blocks in it.
Write heaviestCart(blocks, carts), which returns the smallest possible value of the heaviest cart's load, taken over all such divisions. The return value is an integer.
examples
- case 1
blocks of 7, 2, 5, 10, 8 and carts of 218 — the row divides into 7+2+5 = 14 and 10+8 = 18, and no other division into two consecutive pieces has a smaller heaviest piece - case 2
blocks of 2, 3, 1, 2, 4, 3 and carts of 36 — the pieces 2+3+1 = 6, 2+4 = 6 and 3 = 3; a limit of 5 cannot be met with only three carts - case 3
blocks of 5, 3, 9, 1 and carts of 49 — one block per cart, so the heaviest cart is the heaviest block
- reward
- 360 XP
- signature
heaviestCart
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- two carts on the haul road
- three carts, tight fit
- a single block
- one cart for the whole row
- one cart per block
- five carts down the road
- a heavy block among light ones
- four hundred fifty pebbles
- three hundred thirty slabs