Problem Statement
On the game show "The Price Is Right", some number of contestants are shown a piece of merchandise and are asked to place bids. The contestants bid in order, one after another, and may only bid once. The contestant who bids closest to the actual price of the item, without going over, wins the prize and gets to play another game.
Each contestant uses the following strategy for placing a bid. Let V be equal to the amount that he or she believes the item to be worth. The contestant should bid an amount, B, as low as possible (definitely less than or equal to V) such that no other contestant will bid an amount between B and V, inclusive. Each contestant knows what each of the other contestants think the item is priced at.
Given the amounts at which each contestant values the merchandise, return a list representing the amounts that each player bid on the item.
Definition
- Class:
- PriceIsRight
- Method:
- getBets
- Parameters:
- int[]
- Returns:
- int[]
- Method signature:
- int[] getBets(int[] values)
- (be sure your method is public)
Notes
- The lowest possible bid is $1.
- A contestant is not allowed to make a bid equal to what a previous contestant has bid. If the amount at which a player values the item is equal to a previous bid, that player is unable to bid. You should return -1 (representing "no bid") in his element of the returned int[].
Constraints
- values contains between 1 and 50 elements, inclusive.
- Each element of values will be between 1 and 1000000, inclusive.
- Each element of values will be unique. (That is, no two contestants will value the item at the same price.)
Examples
{50}
Returns: { 1 }
There is only one contestant playing in this game. The player is looking to find a number B such that no other player will bid an amount between B and 50, inclusive. Since there are no other players, it is safe for him to bid the minimum amount, $1.
{50,25}
Returns: { 25, -1 }
Now a second player has joined the game. Player 1 always bids first, and he once again wants to find the lowest possible amount he can safely bid. If he were to bid $1, as he did in the last example, player 2 would cut him off by bidding $2. The same applies for all bids less than $25. If player 1 were to bid $25 exactly, player 2 would be unable to make a bid. Player 1's bid would then go unchallenged. Therefore, this is the lowest safe bid for player 1 to make. Player 2's spot in the array should be -1, since he is unable to make a valid bid.
{50,75}
Returns: { 50, 51 }
For this game, player 2 values the merchandise at $75, which is greater than player 1's value of $50. Thus, no matter what player 1 bids, player 2 will bid an amount one dollar higher. So the only safe bid that player 1 can make is the full $50. Player 2 follows with a bid of $51.
{50, 75, 100}
Returns: { 1, 75, 76 }
The lowest amount that player 1 can bid is $1. This bid is safe because neither of the other contestants will bid an amount between $1 and $50, inclusive. Player 2 needs to bid the full $75 to prevent player 3 from cutting him off. And player 3 can't bid between $1 and $50 because then the $75 bid of player 2 would cut him off. Player 1 bids $1, player 2 bids $75, and player 3 bids $76.
{100,90,80,70,60,50,40,30,20,10}
Returns: { 90, -1, 70, -1, 50, -1, 30, -1, 10, -1 }
The least that player 1 can bid without fear of being overbid is 90. This bid forces player 2 out of the game. Player 3 uses the same strategy as player 1 and bids 70, and player 4 is therefore unable to bid as well. The pattern continues in this manner, with each odd-numbered player bidding 10 less than their estimated value, and each even-numbered player unable to bid.
{50,100,75}
Returns: { 1, 75, -1 }
{75,50,100}
Returns: { 75, 1, 76 }
{75,100,50}
Returns: { 75, 76, 1 }
{100,50,75}
Returns: { 75, 1, -1 }
{100,75,50}
Returns: { 75, -1, 1 }
{1,2,3}
Returns: { 1, 2, 3 }
{1,3,2}
Returns: { 1, 2, -1 }
{2,1,3}
Returns: { 2, 1, 3 }
{2,3,1}
Returns: { 2, 3, 1 }
{3,1,2}
Returns: { 2, 1, -1 }
{3,2,1}
Returns: { 2, -1, 1 }
{432348,777951,696159,13983,30665,507657,183067,775185,331288,103105,154780,835875,471727,964258,973909,420724,840472,738149,261853,978034,155113,84509,601925,70367,790468,691386,492477,515167,356703,540774,550025,775385,527466,424239,962374,600106,118001,708541,191743,915171,413283,351260,927891,963807,746135,166423,291240,697246,325360}
Returns: { 424239, 775385, 696159, 1, 30665, 507657, 183067, 746135, 325360, 84509, 118001, 790468, 471727, 963807, 973909, 413283, 840472, 708541, 261853, 973910, 155113, -1, 601925, 30666, -1, 601926, 471728, 507658, 351260, 527466, 550025, -1, -1, -1, 927891, 550026, -1, -1, 183068, 840473, -1, -1, -1, -1, -1, 155114, 261854, 696160, -1 }
{469305,914699,105557,639365,656289,937977,533036,114985,205260,613573,788721,750520,340890,329974,519644,167371,511482,804772,385534,948849,279596,412782,74442,593307,462677,764174,568362,717261,523676,532593,658858,508516,211678,533284,712691,429292,452525,51222,687442,169346,489442,419231,397136,849102,273662,846112}
Returns: { 462677, 849102, 105557, 613573, 656289, 937977, 533036, 105558, 205260, -1, 764174, 717261, 329974, -1, 511482, 167371, -1, 804772, 385534, 937978, 273662, 412782, 51222, 568362, -1, -1, -1, -1, 523676, 523677, 656290, 489442, 205261, 533037, 687442, 429292, 429293, -1, -1, 167372, -1, 412783, 385535, -1, -1, 804773 }
{427023,994670,6269,515357,293938,228154,53132,382822,917373,930360,478982,757860,84497,802279,993353,74368,806114,874001,318472,728161,207285,832841,204890,30090,667953,601470,697100,409171,213572,166031,649169,865709,155724,654271,490356,674424,982752,663664,240741,337574,500382,839534,776851,788082,222346,703183}
Returns: { 427023, 993353, 6269, 515357, 240741, 222346, 53132, 382822, 874001, 930360, 427024, 757860, 84497, 788082, -1, 53133, 806114, -1, 318472, 703183, 207285, 806115, 166031, 6270, 663664, 515358, 674424, 382823, 207286, -1, 649169, 839534, 84498, 649170, 490356, -1, 930361, -1, -1, 318473, 490357, -1, 757861, -1, -1, -1 }
{620061,620029,620041,620116,620087,620078,620117,620071,620084,620043,620064,620055,620077,620049,620092,620053,620111,620028,620099,620097,620045,620052,620081,620076,620104,620107,620096,620080,620119,620090,620065,620100,620039,620098,620095,620038,620083,620034,620056,620033,620050,620088,620044,620094}
Returns: { 620061, 620028, 620041, 620111, 620084, 620078, 620117, 620065, -1, 620042, 620062, 620055, 620076, 620049, 620092, 620052, -1, -1, 620099, 620097, 620044, -1, 620081, -1, 620104, 620105, 620095, 620079, 620118, 620088, -1, 620100, 620038, 620098, -1, -1, 620082, 620033, 620056, -1, 620050, -1, -1, 620093 }
{378680,378723,378691,378704,378706,378716,378683,378712,378695,378726,378709,378671,378692,378725,378682,378694,378686,378721,378673,378696,378722,378675,378674,378710,378685,378693,378703,378698}
Returns: { 378680, 378722, 378686, 378703, 378706, 378716, 378683, 378710, 378694, 378725, 378707, 378671, 378692, -1, 378681, -1, -1, 378717, 378672, 378696, -1, 378674, -1, -1, 378684, 378693, -1, 378697 }
{165414,165421,165407,165387,165391,165416,165418,165402,165401,165415,165413,165392,165389,165409,165417,165393,165411,165399}
Returns: { 165414, 165418, 165407, 165387, 165391, 165416, -1, 165401, -1, 165415, 165411, 165392, 165388, 165408, 165417, 165393, -1, 165394 }
{ 100, 35, 85, 12, 295, 183, 79, 44, 54, 64, 74, 84, 94, 104, 114, 37 }
Returns: { 94, 12, 84, -1, 183, -1, 74, 37, 54, 55, -1, -1, -1, 104, 105, -1 }
{ 30, 10, 20, 40 }
Returns: { 30, 10, 11, 31 }
{ 10, 9, 8, 7, 52, 63, 96, 323, 525, 636, 787, 989, 1000, 900, 800, 700, 600, 500, 400, 300, 200, 100, 50, 25, 126, 106 }
Returns: { 9, -1, 7, -1, 52, 53, 96, 323, 500, 600, 700, 989, 990, 800, -1, -1, -1, -1, 324, 200, -1, 97, 25, -1, 106, -1 }
{ 41, 18467, 6334, 26500, 19169, 15724, 11478, 29358, 26962, 24464, 5705, 28145, 23281, 16827, 9961, 491, 2995, 11942, 4827, 5436, 32391, 14604, 3902, 153, 292, 12382, 17421, 18716, 19718, 19895, 5447, 21726, 14771, 11538, 1869, 19912, 25667, 26299, 17035, 9894, 28703, 23811, 31322, 30333, 17673, 4664, 15141, 7711, 28253, 6868 }
Returns: { 41, 17673, 6334, 26299, 18716, 15724, 9961, 29358, 26962, 24464, 5447, 26963, 23281, 15725, -1, 292, 1869, 11538, 4827, 4828, 31322, 12382, 3902, 42, -1, -1, 17035, -1, 19718, 19719, -1, 19912, 14771, -1, -1, -1, 24465, -1, -1, 7711, 28253, 23282, -1, 29359, -1, 3903, 14772, -1, -1, 6335 }
{ 50, 200, 100 }
Returns: { 1, 100, -1 }
{ 47, 57, 90, 5 }
Returns: { 5, 57, 58, -1 }
{ 10, 20, 30, 40, 50, 51, 61, 62, 70, 80, 90, 100, 200, 201, 301, 2, 500 }
Returns: { 10, 11, 30, 31, 50, 51, 61, 62, 70, 71, 90, 91, 200, 201, 301, 1, 302 }
{ 50, 75, 100 }
Returns: { 1, 75, 76 }
{ 11, 5, 3, 10, 15 }
Returns: { 11, 5, 1, 6, 12 }
{ 1, 50, 200, 100 }
Returns: { 1, 2, 100, -1 }
{ 5, 4, 6, 7 }
Returns: { 4, -1, 6, 7 }