DieDesign
TCO19 SRM 740 · 2018-10-19 · by misof
Problem Statement
Yves and Zola are playing dice.
Yves has one N-sided die.
You are given the
Zola has a blank N-sided die and a permanent marker she can use to draw pips onto her die. She can distribute the pips arbitrarily, but to keep it fair, the total number of pips she draws must be exactly equal to the total number of pips on Yves's die.
Once Zola finishes her die, they will both roll their die and higher score wins. As the way the dice were chosen gives an advantage to Zola, Yves wins ties.
Design Zola's die. Maximize the probability that she wins.
Return a
Notes
- The limit of 5000 pips per side only applies to Yves's die. Zola may place more than 5000 pips on some sides of her die, if she wants to.
Constraints
- pips will have between 1 and 30 elements, inclusive.
- Each element of pips will be between 0 and 5000, inclusive.
{1,2,3,4,5,6}
Returns: {0, 0, 0, 7, 7, 7 }
Sometimes this game happens to be perfectly fair. With the die we designed for Zola she will win 50 percent of all games.
{0,0,0,2}
Returns: {0, 0, 1, 1 }
Having the two pips on different faces is much better for Zola than having the same die as Yves.
{1,1,13,1}
Returns: {4, 4, 4, 4 }
Sometimes Zola's die will turn out to be the better one of the pair.
{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,4963,4964,4965,4966,4967,4968,4969,4970,4971,4972,4973,4974,4975,4976,4977,4978,4979}
Returns: {231, 257, 257, 257, 257, 257, 257, 257, 257, 257, 257, 257, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980, 4980 }
{1,3,9,27,81,243,729,2187}
Returns: {600, 244, 244, 244, 244, 244, 730, 730 }
Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DieDesign with a public method vector<int> design(vector<int> pips) · 108 test cases · 2 s / 256 MB per case