Spend a retry budget on an agent's failed tasks

Your coding agent failed a batch of tasks overnight, and you can afford a fixed number of retries. Past runs tell you how often a new attempt at each task passes its tests. Attempts run one at a time, and you see each result before you choose the next.

Write expected_passes(pass_rates, budget) that returns the expected number of tasks that pass when every attempt is chosen as well as possible.

Input and output:

• pass_rates: up to 1,000 whole numbers from 0 to 100. An attempt at task i passes with chance pass_rates[i] percent.
• budget: the most attempts you can make in total, a whole number from 0 to 1,000.
• Return a float. The tests accept any value within 0.000001 of the exact one.

Rules:

• Each attempt passes or fails independently of every other attempt, with its task's chance.
• A task that has passed needs no more attempts. A task may be attempted any number of times.
• Before each attempt, you know which tasks have passed so far, and you pick the task to try next, or stop.
• The expected number of passing tasks is the average over every way the attempts can turn out. Choose the attempts to make it as large as possible, and return that largest value.