Maximize the minimum asset value within an upgrade budget

You hold a portfolio of n assets. Asset i is currently worth values[i]. You can upgrade any asset as many times as you like. Each upgrade of asset i costs costs[i] and adds values[i] to its worth, so after k upgrades asset i is worth values[i] * (1 + k).

You have a total upgrade budget budget. Spend at most budget so that the lowest final worth across all assets (the portfolio's floor) is as high as possible. Return that floor.

def max_floor_value(values: list[int], costs: list[int], budget: int) -> int: ...

Constraints

• 1 <= n <= 10^5
• 1 <= values[i] <= 10^9, 1 <= costs[i] <= 10^9
• 0 <= budget <= 10^14
• Upgrades are whole steps. You do not have to spend the whole budget.

Example 1

values = [3, 5, 2], costs = [2, 1, 3], budget = 7
output: 4

Upgrade asset 0 once (cost 2, worth 6) and asset 2 once (cost 3, worth 4). The worths are [6, 5, 4]. A floor of 5 would need two upgrades on asset 2 (cost 6) plus one on asset 0 (cost 2), which is 8 and over budget.

Example 2

values = [1, 1, 1], costs = [1, 1, 1], budget = 5
output: 2

Upgrading each asset once (cost 3) gives a floor of 2. A floor of 3 needs two upgrades on every asset (cost 6).

Part 2. Also return how many times to upgrade each asset to reach the optimal floor.

Reconstructed from the reported question; details may differ from what interviewers ask.