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 a int[] 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 int[] of bids, determine the indices of the winning bids. The first element of bids has an index of 1.
Definition
- Class:
- Auction
- Method:
- winners
- Parameters:
- int[]
- Returns:
- int[]
- Method signature:
- int[] winners(int[] bids)
- (be sure your method is public)
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
{4, 5, 10000}Returns: { 2, 3 }{5, 5, 5, 5}Returns: { }{10000, 10000, 1000, 1000, 1, 1, 10, 10, 100, 100}Returns: { 1, 2 }{4, 2, 2, 3, 4, 1}Returns: { 1, 4, 5 }
Back to all problems