Show problems as
Classic problem #2861MediumArrayBinary Search

Maximum Number of Alloys

Real-world version: Poster Run on One Press
Tracked in this browser only
Read Maximum Number of Alloys on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A print shop is quoting a run of identical posters. It keeps inks different inks, numbered 0 to inks - 1, and presses presses, numbered 0 to presses - 1.

Press i is plumbed for its own mix: turning out one poster on it consumes exactly recipe[i][j] grams of ink j, for every ink j. The shop already holds onhand[j] grams of ink j, which cost nothing to use, and it can order any whole number of extra grams of ink j at price[j] per gram. The total order may cost at most budget.

The whole run has to come off a single press; posters cannot be split between presses. Ink left over is simply left over, and it can never be sold or traded towards the cost of a different ink.

Return the largest number of posters the shop can turn out.

Examples

Example 1

Input
inks = 2, presses = 2, budget = 30, recipe = [[2, 1], [1, 3]], onhand = [6, 8], price = [4, 2]
Output
7

Press 1 turns out seven posters: it needs 7 grams of ink 0 and 21 of ink 1, so the shop orders 1 gram of ink 0 for 4 and 13 grams of ink 1 for 26, spending 30 in total.

Example 2

Input
inks = 3, presses = 1, budget = 0, recipe = [[1, 2, 1]], onhand = [10, 7, 12], price = [3, 3, 3]
Output
3

Nothing can be ordered, so the run is capped by the ink already in the cupboard; ink 1 runs out first at three posters.

Example 3

Input
inks = 2, presses = 1, budget = 6, recipe = [[1, 1]], onhand = [20, 0], price = [5, 2]
Output
3

Ink 0 is plentiful and ink 1 is bare, so every poster needs a gram of ink 1 ordered at 2, and the budget of 6 covers three of them.

Constraints

  • 1 <= inks, presses <= 100
  • 0 <= budget <= 10^8
  • recipe.length == presses
  • recipe[i].length == inks
  • 1 <= recipe[i][j] <= 100
  • onhand.length == price.length == inks
  • 0 <= onhand[j] <= 10^8
  • 1 <= price[j] <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def most_posters(inks: int, presses: int, budget: int, recipe: list[list[int]], onhand: list[int], price: list[int]) -> int:
Java
public int mostPosters(int inks, int presses, int budget, List<List<Integer>> recipe, List<Integer> onhand, List<Integer> price)

More on the same topics