Welcome set budget
A conference buys a welcome set for every attendee, and each supplier covers one item in that set. Supplier i sells only in sealed packs holding pack_sizes[i] items at pack_cents[i] cents a pack, and a part used pack still costs a whole pack, so serving n attendees costs ceil(n / pack_sizes[i]) * pack_cents[i] at that supplier, added up over every supplier. Return the largest number of attendees the order can cover without the total passing budget_cents. The hall seats 100000 people, so never return more than 100000, and the answer never drops below 0, since serving nobody costs nothing. Pack sizes are at least 1, pack prices and the budget are never negative, and an order listing no suppliers at all costs nothing. Pricing one headcount touches every supplier, so halve the range rather than trying every headcount in turn.
largest_affordable_headcount(pack_sizes: list[int], pack_cents: list[int], budget_cents: int) → int[[10,25],[300,500],10000]out200[[5],[100],199]out5[[],[],0]out100000State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[10,25],[300,500],10000]200not run yetsample[[5],[100],199]5not run yetsample[[],[],0]100000not run yetsample