Maximize Buying Goodies

EasyPython

Problem

Postman provides a list of goodies with different prices. You have some initial money and may sell one printer cartridge for additional cash. Determine the maximum number of distinct goodies you can buy after adding the cartridge sale proceeds to your budget.

Each goodie can be bought at most once, and you may choose any subset. The sale is optional, but the cartridge sale value is non-negative and selling it has no transaction cost.

Formal Specification

Implement max_goodies(prices, money, cartridge_value), where:

prices is a list of positive integers representing goodie prices.
money is a non-negative integer representing your initial budget.
cartridge_value is a non-negative integer representing the money received from selling the cartridge.
Return an integer representing the maximum number of goodies that can be purchased.

Because every goodie contributes exactly one to the objective, the optimal purchase set consists of the cheapest affordable goodies.

Constraints

1 <= len(prices) <= 2 * 10^5
1 <= prices[i] <= 10^9
0 <= money <= 10^14
0 <= cartridge_value <= 10^14
Each goodie can be purchased at most once

Function Signature

def max_goodies(prices, money, cartridge_value):

Each goodie can be bought at most once, and you may choose any subset. The sale is optional, but the cartridge sale value is non-negative and selling it has no transaction cost.

Formal Specification

Implement max_goodies(prices, money, cartridge_value), where:

prices is a list of positive integers representing goodie prices.
money is a non-negative integer representing your initial budget.
cartridge_value is a non-negative integer representing the money received from selling the cartridge.
Return an integer representing the maximum number of goodies that can be purchased.

Because every goodie contributes exactly one to the objective, the optimal purchase set consists of the cheapest affordable goodies.