Jackpots#11316

Jackpots (Editorial)

Let us imagine that the player immediately drew all the balls in a random order. In other words, we obtained a random permutation of $n = a + b + c$ n = a + b + c balls. The game ends when one of the colors runs out for the first time. Therefore, the winning color is the one whose last ball appears earliest in the permutation.

Let us calculate the probability of winning the golden jackpot. For red to win, the last ball in the sequence must be either green or blue. Let us consider both cases.

Case А: The probability that the last ball in the sequence is green is $b / n$ (there are $b$ green balls out of $n$ balls). Green has lost. Only red and blue balls remain, and we need to determine which of them wins.

Mentally remove all green balls from the sequence and consider only the red and blue balls (there are $a + c$ a + c of them). Red wins if the last ball among the red and blue balls is blue. The probability that the last among these $a + c$ a + c balls is blue is $c / (a + c)$ c / (a + c). Each of these balls is equally likely to be the last one, and there are $c$ blue balls among them.

The probability of Case $A$ is $\frac{b}{n} \cdot \frac{c}{a + c}$ \frac{b}{n} \cdot \frac{c}{a+c}.

Case B: The probability that the last ball in the sequence is blue is $c / n$ (there are $c$ blue balls out of $n$ balls). Blue has lost. Remove the blue balls and consider the red and green balls (there are $a + b$ a + b of them). Red wins if the last ball among them is green. The probability of this is $b / (a + b)$ b / (a + b).

The probability of Case $B$ is $\frac{c}{n} \cdot \frac{b}{a + b}$ \frac{c}{n} \cdot \frac{b}{a+b}.

Cases $A$ and $B$ are mutually exclusive (the last ball cannot be both green and blue), so the probability that red wins is

p_{G} = \frac{b}{n} \cdot \frac{c}{a + c} + \frac{c}{n} \cdot \frac{b}{a + b}

p_G = \frac{b}{n} \cdot \frac{c}{a+c} + \frac{c}{n} \cdot \frac{b}{a+b}

Similarly, the probability that green wins is

p_{S} = \frac{a}{n} \cdot \frac{c}{b + c} + \frac{c}{n} \cdot \frac{a}{a + b}

p_S = \frac{a}{n} \cdot \frac{c}{b+c} + \frac{c}{n} \cdot \frac{a}{a+b}

The probability that blue wins is

p_{B} = \frac{a}{n} \cdot \frac{b}{b + c} + \frac{b}{n} \cdot \frac{a}{a + c}

p_B = \frac{a}{n} \cdot \frac{b}{b+c} + \frac{b}{n} \cdot \frac{a}{a+c}

Example

Let's consider the second test case ( $a = 1, b = 2, c = 3, n = a + b + c = 6$ a = 1, b = 2, c = 3, n = a + b + c = 6). Let us calculate the probabilities of winning the jackpots:

p_{G} = \frac{b}{n} \cdot \frac{c}{a + c} + \frac{c}{n} \cdot \frac{b}{a + b} = \frac{2}{6} \cdot \frac{3}{4} + \frac{3}{6} \cdot \frac{2}{3} = \frac{1}{4} + \frac{1}{3} = \frac{7}{12}, p_{S} = \frac{a}{n} \cdot \frac{c}{b + c} + \frac{c}{n} \cdot \frac{a}{a + b} = \frac{1}{6} \cdot \frac{3}{5} + \frac{3}{6} \cdot \frac{1}{3} = \frac{1}{10} + \frac{1}{6} = \frac{4}{15}, p_{B} = \frac{a}{n} \cdot \frac{b}{b + c} + \frac{b}{n} \cdot \frac{a}{a + c} = \frac{1}{6} \cdot \frac{2}{5} + \frac{2}{6} \cdot \frac{1}{4} = \frac{1}{15} + \frac{1}{12} = \frac{3}{20}

p_G = \frac{b}{n} \cdot \frac{c}{a+c} + \frac{c}{n} \cdot \frac{b}{a+b} = \frac{2}{6} \cdot \frac{3}{4} + \frac{3}{6} \cdot \frac{2}{3} = \frac{1}{4} + \frac{1}{3} = \frac{7}{12}, \\ p_S = \frac{a}{n} \cdot \frac{c}{b+c} + \frac{c}{n} \cdot \frac{a}{a+b} = \frac{1}{6} \cdot \frac{3}{5} + \frac{3}{6} \cdot \frac{1}{3} = \frac{1}{10} + \frac{1}{6} = \frac{4}{15}, \\ p_B = \frac{a}{n} \cdot \frac{b}{b+c} + \frac{b}{n} \cdot \frac{a}{a+c} = \frac{1}{6} \cdot \frac{2}{5} + \frac{2}{6} \cdot \frac{1}{4} = \frac{1}{15} + \frac{1}{12} = \frac{3}{20}

Algorithm implementation

The gcd function computes the greatest common divisor of the numbers $a$ and $b$ .

long long gcd(long long a, long long b)
{
  return b == 0 ? a : gcd(b, a % b);
}

The solve function computes the probability that the red balls win.

string solve(int a, int b, int c)
{
  int n = a + b + c;
  int q1 = n * (a + c);
  int q2 = n * (a + b);
  long long p = (long long)b * c * (q1 + q2);
  long long q = (long long)q1 * q2;
  long long g = gcd(p, q);
  return to_string(p / g) + "/" + to_string(q / g);
}

C++

The main part of the program. Read the input data.

cin >> a >> b >> c;

Compute and print the answer. Note that the function calls:

$so l v e (a, b, c)$ solve(a, b, c) compute the probability that the red balls win;
$so l v e (b, c, a)$ solve(b, c, a) compute the probability that the green balls win;
$so l v e (c, a, b)$ solve(c, a, b) compute the probability that the blue balls win;

cout << solve(a, b, c) << " " << solve(b, c, a) << " "
     << solve(c, a, b) << endl;