Connection Status:
Competition Arena > Conditional

Conditional

SRM 304 · 2006-05-27 · by dgoodman

SRM 304 · 2006-05-27 · by dgoodman · Dynamic Programming, Math
Class Name: Conditional
Return Type: double
Method Name: probability
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

Conditional probability can be illustrated with dice problems. What is the probability that you rolled a 12 on a pair of normal 6-sided dice, given that at least one of the dice shows a 6? This is the same question as the following: roll a pair of dice until at least one of the dice shows 6 -- what is the probability that your final roll has 6 on BOTH dice. The surprising answer is 1/11 since of the 36 equally likely rolls, 11 have at least one 6 and 1 of these 11 has 6 on both dice.

Our goal is to solve a generalized version of this problem in which we roll nDice identical dice, each with sides labelled 1,2,...,maxSide. We want to know the probability that the sum of the dice is greater than or equal to theSum given that at least one of the dice shows the value v. Create a class Conditional that contains a method probability that is given nDice,maxSide, v, and theSum and that returns the desired conditional probability.

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

  • nDice and maxSide will be between 1 and 50, inclusive.
  • v will be between 1 and maxSide, inclusive.
  • theSum will be between 1 and maxSide*nDice, inclusive.
Examples
0)
2
6
6
12
Returns: 0.09090909090909091

This is the example above whose answer is 1/11. (Of course, the sum cannot be greater than 12.)

1)
2
6
6
6
Returns: 1.0

Given that at least one of the dice shows a 6 the sum of the 2 dice must be at least 7.

2)
1
9
3
3
Returns: 1.0
3)
2
3
2
4
Returns: 0.6

Two 3-sided (!) dice with at least one 2 showing: 12 22 32 21 23 are the 5 possible equally likely results, and 3 of the 5 have a sum greater than or equal to 4.

4)
50
50
50
1
Returns: 0.9999999999999967

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

Coding Area

Language: C++17 · define a public class Conditional with a public method double probability(int nDice, int maxSide, int v, int theSum) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous