Reroll | Topcoder Archive

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:

Your opponent chooses a positive integer target (between n and 6n, inclusive).
You roll all n dice.
You select any subset of the dice you rolled and you reroll them.
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:

She wants to have a chance to win the game.
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.

Definition

Class:: Reroll
Method:: minimumDice
Parameters:: int, int[]
Returns:: int
Method signature:: int minimumDice(int target, int[] dice)
(be sure your method is public)

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

```
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.
```
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.
```
42
```
```
{6,6,6,6,6,6,6}
```
```
Returns: 0
```
Monika has already won - no need to reroll anything.
```
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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.