The Grimoire-Copyists of Vellumhaugh Abbey
The Abbess of Vellumhaugh holds the only surviving copy of the *Codex Ashenward*, a grimoire of binding-rites, and its ink is fading fast. The Guild of Quiet Hands is commissioned to copy it before the codex is lost. The copyists work in parallel at the same pace, so the copying lasts as long as the heaviest share given to any one copyist.
The grimoire's chapters are given in order as pages, a list of positive integers where pages[i] is the page count of chapter i. There are scribes copyists, an integer of at least 1.
The chapters are divided under these rules: - Every chapter is copied whole by exactly one copyist. A chapter is never split. - Each copyist takes one contiguous run of chapters. The order of the chapters is never changed. - A copyist may be given no chapters at all.
A copyist's load is the total number of pages in their chapters.
Write heaviestShare(pages, scribes), which returns an integer: the smallest possible value of the largest load, taken over all valid ways to divide the chapters. If pages is empty, return 0.
examples
- case 1
pages of [7, 2, 5, 10, 8], scribes of 218 — the first copyist takes 7 + 2 + 5 = 14 pages and the second takes 10 + 8 = 18 pages - case 2
pages of [3, 1, 4, 1, 5], scribes of 105 — each chapter gets its own copyist, and the five extra copyists sit idle - case 3
pages of [], scribes of 30 — there is nothing to copy
- reward
- 320 XP
- signature
heaviestShare
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- classic two copyists
- ascending chapters, two copyists
- uneven tail favours early split
- empty grimoire
- single chapter single copyist
- more copyists than chapters
- one copyist takes everything
- giant chapter dominates
- three copyists mixed chapters
- ten equal pages three copyists
- equal chapters fewer copyists
- exactly one copyist per chapter