Auction
SRM 106 · 2002-07-29 · by axchma
SRM 106 · 2002-07-29 · by axchma
Problem Statement
Problem Statement
I have a collection of counter-intuitive math problems and have compiled a list of the most famous ones with my solutions and analyses. I plan to
donate an unlimited number of autographed copies of this list to a charitable
auction. I have two restrictions for the arrangement of the auction. Namely, I
would like people to be able to bid by e-mail and I would like the auction to
be envy-free: that is, all the winners should pay the same price. Here is the
protocol of the auction, carried out in this order:
1) I receive all the bids.
2) I choose one bid, say of M dollars, to become the highest non-winning bid.
3) Everybody who bids more than M dollars becomes a winner and receives a copy of my paper for the price of M dollars. If N people bid more than M dollars, then the profit from the auction is M x N.
Two things to keep in mind:
- I choose the highest non-winning bid to maximize the profit.
- The cost for me per unit is 0.
- If I have several options for the same profit, I prefer to be generous and choose the option with the largest number of winning bids. Your task is, given aint[] of bids, determine the indices of the winning
bids. The first element of bids has an index of 1.
1) I receive all the bids.
2) I choose one bid, say of M dollars, to become the highest non-winning bid.
3) Everybody who bids more than M dollars becomes a winner and receives a copy of my paper for the price of M dollars. If N people bid more than M dollars, then the profit from the auction is M x N.
Two things to keep in mind:
- I choose the highest non-winning bid to maximize the profit.
- The cost for me per unit is 0.
- If I have several options for the same profit, I prefer to be generous and choose the option with the largest number of winning bids. Your task is, given a
Notes
- There must always be at least one non-winning bid. One consequence of this is that if all the bids are the same, there is no winner.
Constraints
- bids has between 1 and 50 elements, inclusive.
- Each element of bids is between 1 and 10000, inclusive.
Examples
0)
{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Returns: { 1, 2, 3, 4, 5 }
1)
{4, 5, 10000}
Returns: { 2, 3 }
2)
{5, 5, 5, 5}
Returns: { }
3)
{10000, 10000, 1000, 1000, 1, 1, 10, 10, 100, 100}
Returns: { 1, 2 }
4)
{4, 2, 2, 3, 4, 1}
Returns: { 1, 4, 5 }
Submissions are judged against all 37 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Auction with a public method vector<int> winners(vector<int> bids) · 37 test cases · 2 s / 256 MB per case