Connection Status:
Competition Arena > Reroll

Reroll

SRM 736 *TCO19* · 2018-08-14 · by majk

SRM 736 *TCO19* · 2018-08-14 · by majk · Brute Force, Math, Simulation
Class Name: Reroll
Return Type: int
Method Name: minimumDice
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

This problem is about dice. All dice in this problem are the standard six-sided dice with numbers 1 through 6 on their faces.

Consider the following game that is played with n dice:

  1. Your opponent chooses a positive integer target (between n and 6n, inclusive).
  2. You roll all n dice.
  3. You select any subset of the dice you rolled and you reroll them.
  4. You add the numbers that are now shown on the n dice. If the sum is exactly equal to target, you win, otherwise you lose.

This game is often played as a drinking game with one extra rule: for each die you rerolled in step 3 you have to drink a shot.

Monika is playing this game. Her priorities are as follows:

  1. She wants to have a chance to win the game.
  2. She wants to drink as few shots as possible.

You are given the int target. You are also given the int[] dice. The elements of dice are the values rolled by Monika in step 2 of the game. Monika is now in step 3. Compute and return the smallest number of shots she will have to drink in order to have a positive probability to win the game.

Constraints

  • target will be between n and 6n, inclusive, where n is the number of elements in dice.
  • dice will contain between 1 and 20 elements, inclusive.
  • Each element of dice will be between 1 and 6, inclusive.
Examples
0)
7
{2,6,4}
Returns: 1

The current sum is 12. In order to have a shot at having sum of 7, Monika has to reroll the 6 and hope for a 1.

1)
10
{4,2,4,5}
Returns: 2

The current sum is 15. Monika can choose, for instance, to reroll the two fours. She will win if she gets a 1 and a 2.

2)
42
{6,6,6,6,6,6,6}
Returns: 0

Monika has already won - no need to reroll anything.

3)
42
{1,3,5,3,6,4,2}
Returns: 6

Out of all the dice, just the single 6 is useful. Monika has to reroll all other dice and hope they all land a six.

4)
120
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 20

Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Reroll with a public method int minimumDice(int target, vector<int> dice) · 68 test cases · 2 s / 256 MB per case

Submitting as anonymous