A harbour charity sells a painting of the old lighthouse by sealed bids: every bidder writes one amount in whole dollars, seals it in an envelope, and nobody sees the other envelopes. Bidder i (in the order the envelopes arrived) bids bids[i]. The charity sets a reserve price reserve: a bid below the reserve is thrown out.
Among the bids that are at least reserve, the highest bid wins. If several bidders tie for the highest bid, the one who handed in their envelope first (the smallest index) wins. The charity has not yet decided how the winner pays, so it wants both answers:
- First-price rule: the winner pays their own bid.
- Second-price (Vickrey) rule: the winner pays the highest bid among the other bidders that is at least
reserve, orreserveitself if there is no such bid. (On a tie this is the tied amount.)
Write sealed_auction(bids, reserve) that returns the tuple (winner, first_price, second_price): the winner's index and the two payments. If no bid reaches the reserve, the painting is not sold: return (None, 0, 0).
Examples
Input: bids = [120, 340, 275, 90], reserve = 100
Output: (1, 340, 275)
Explanation: bidder 1 bids the most; the best other bid is 275.
Input: bids = [60, 140, 40], reserve = 100
Output: (1, 140, 100)
Explanation: only bidder 1 reaches the reserve, so under the second-price rule they pay the reserve.
Input: bids = [50, 80, 80], reserve = 0
Output: (1, 80, 80)
Explanation: bidders 1 and 2 tie; bidder 1's envelope came first.
Goals
- Find the winner of a sealed-bid auction with a reserve price and a stated tie rule
- Compute what the winner pays under the first-price rule and under the second-price (Vickrey) rule
- Handle an auction where no bid reaches the reserve