772. How Many Alloys the Budget Buys
A workshop has n machines and works with k kinds of metal. Machine i turns
comp[i][j] units of metal j into ONE alloy, consuming all k metals in the amounts its own
row gives.
You already hold stock[j] units of metal j free of charge, and you may buy any further
units of metal j at cost[j] each. Your budget is budget.
Every alloy must be produced on the SAME machine; you pick which machine before you start. Print the largest number of alloys you can produce.
2 machines, 2 metals, budget 100
comp = (1 2) and (2 1), stock = 10 10, cost = 1 1 answer 40
1 machine, 1 metal, budget 10, comp = 1, stock = 100, cost = 1 answer 110
1 machine, 1 metal, budget 0, comp = 1, stock = 0, cost = 1 answer 0
1 machine, 2 metals, budget 7, comp = (3 1), stock = 0 0, cost = 1 1 answer 1
## Why this is a search and not a formula
Because the stock is free, the cost per alloy is not constant. The first few alloys may be free and the rest paid for, and the changeover happens at a different count for each metal. Dividing the budget by anything gives the wrong number.
What you CAN do easily is price a specific plan.
## The cost of producing exactly c alloys on machine i
Machine i needs c * comp[i][j] units of metal j in total. Of those, stock[j] are free,
so the units to buy are max(0, c * comp[i][j] - stock[j]), and
price(i, c) = sum over j of max(0, c * comp[i][j] - stock[j]) * cost[j]
feasible(i, c) = price(i, c) <= budget
## Why this is exact rather than greedy
There is no allocation decision to make. Producing c alloys on machine i consumes a fixed
amount of every metal, stock is used before anything is bought because stock is free, and the
metals do not compete with each other. So price(i, c) is not the best guess at a plan, it is
the only possible cost of that plan.
The only real decision is WHICH MACHINE, and there are only n of those, so try each one and
take the best. That outer loop is the whole difference between this and a single search.
## Why the predicate is monotone
c * comp[i][j] grows with c, so each term max(0, c * comp[i][j] - stock[j]) is
non-decreasing, and cost[j] is positive. So price(i, c) is non-decreasing in c, and
affordability flips from true to false exactly once. For a fixed machine the answer is the LAST
affordable c, so the midpoint rounds UP.
## The bounds
lo = 0, always affordable, since producing nothing costs nothing.
hi = max(stock) + budget. To see why this can never be beaten: every alloy needs at least one
unit of every metal, because comp[i][j] >= 1. Take any metal j. Producing c alloys needs
at least c units of it, of which at most stock[j] are free, so at least c - stock[j] are
bought at cost[j] >= 1 each, costing at least c - stock[j]. That must be within budget, so
c <= stock[j] + budget <= max(stock) + budget.
A loose bound like 10^18 would still terminate, but it would make the products inside
price overflow, so the bound is doing real work here.
## The boundary that breaks a careless implementation
The max(0, ...) guard. Without it a metal you hold more of than you need contributes a
NEGATIVE cost and pays for the others. One of the tests holds 10^8 units of the first metal
and none of the other two; with the clamp the answer is 5000, and without it the surplus of the
first metal subsidises the other two and the reported answer climbs past 300000.
With a single metal the bug is invisible, because there is nothing for the surplus to pay for. That is why it survives casual testing.
The second trap is the order of arithmetic. Compute c * comp - stock first and multiply by
cost afterwards, and stop adding the moment the running total passes budget. Multiplying
comp * cost first and scaling later changes nothing mathematically but makes the intermediate
values larger for no reason.
## Relationship with problem 766
766 is built on the same clamped sum. Its yield is sum of max(0, a[i] - h) and this price is
sum of max(0, c * comp[i][j] - stock[j]) * cost[j], and in both the clamp is what makes the
function non-linear: trees leave 766's sum one at a time as the blade rises, and metals enter
this one's sum one at a time as the count grows.
The two run in opposite directions and still produce the same search. 766's yield FALLS as h
rises while this price CLIMBS as c rises, yet the workable values form a prefix either way, so
both take the last true value and both round the midpoint up. The real difference is the outer
loop: 766 searches once, this searches once per MACHINE and keeps the best, because no threshold
can decide which machine to use.
## Overflow
With c as large as 2 * 10^8, comp up to 100 and cost up to 100, a single term reaches
2 * 10^12 and the sum over 100 metals reaches 2 * 10^14. Every one of those products
must be computed in 64-bit. In 32 bits the very first multiplication wraps, the price looks
affordable, and the reported answer is the upper bound itself.
## Cost
O(n k log(max stock + budget)).
Constraints - `1 ≤ n ≤ 100` - `1 ≤ k ≤ 100` - `1 ≤ comp[i][j] ≤ 100` - `0 ≤ stock[j] ≤ 10^8` - `1 ≤ cost[j] ≤ 100` - `0 ≤ budget ≤ 10^8`
Input
The first line contains three integers n, k and budget.
Each of the next n lines contains k integers: row i is the amount of each metal machine
i needs per alloy.
The next line contains k integers, the free stock of each metal.
The last line contains k integers, the unit cost of each metal.
Output
Print one integer on its own line: the largest number of alloys producible on a single machine within the budget. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.