Джекпоти#11316

Джекпоти (Розбір)

Уявімо, що гравець одразу витягнув усі кульки у випадковому порядку, тобто отримали випадкову перестановку з $n = a + b + c$ n = a + b + c кульок. Гра закінчується, коли вперше закінчився якийсь колір. Отже, перемагає той колір, чия остання кулька стоїть у перестановці раніше за всіх.

Обчислимо ймовірність золотого джекпоту. Щоб червоний виграв, остання кулька ряду має бути зеленою або синьою. Розберемо обидва випадки.

Випадок А: Ймовірність того, що остання кулька ряду зелена, дорівнює $b / n$ (зелених кульок $b$ штук із $n$ ). Зелені програли. Залишилися червоні та сині, і треба зрозуміти, хто з них переможе.

Умовно викинемо зелені кульки з ряду та подивимось лише на червоні й сині (їх $a + c$ a + c штук). Червоний переможе, якщо найостанніша серед червоних і синіх кульок — синя. Ймовірність того, що остання серед $a + c$ a + c кульок синя, дорівнює $c / (a + c)$ c / (a + c). Кожна з цих кульок з однаковою ймовірністю може опинитись останньою, а синіх серед них $c$ штук.

Ймовірність Випадку $A$ дорівнює $\frac{b}{n} \cdot \frac{c}{a + c}$ \frac{b}{n} \cdot \frac{c}{a+c}.

Випадок B: Ймовірність того, що остання кулька ряду синя, дорівнює $c / n$ (синіх кульок $c$ штук із $n$ ). Сині програли. Викидаємо сині та дивимось на червоні й зелені (їх $a + b$ a + b штук). Червоний переможе, якщо останньою серед них виявилась зелена, ця ймовірність дорівнює $b / (a + b)$ b / (a + b).

Ймовірність Випадку $Б$ дорівнює $\frac{c}{n} \cdot \frac{b}{a + b}$ \frac{c}{n} \cdot \frac{b}{a+b}.

Випадки $A$ і $B$ не перетинаються (остання кулька не може бути одночасно й зеленою, і синьою), тому ймовірність перемоги червоних становитиме

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}

Аналогічно ймовірність перемоги зелених дорівнює

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}

Ймовірність перемоги синіх дорівнює

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}

Приклад

Розглянемо другий тест ( $a = 1, b = 2, c = 3, n = a + b + c = 6$ a = 1, b = 2, c = 3, n = a + b + c = 6). Обчислимо ймовірності виграшів джекпотів:

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}

Реалізація алгоритму

Функція gcd обчислює найбільший спільний дільник чисел $a$ і $b$ .

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

Функція solve обчислює ймовірність перемоги червоних.

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++

Основна частина програми. Зчитуємо вхідні дані.

cin >> a >> b >> c;

Обчислюємо та виводимо відповідь. Зазначимо, що виклик функції:

$so l v e (a, b, c)$ solve(a, b, c) обчислює ймовірність перемоги червоних;
$so l v e (b, c, a)$ solve(b, c, a) обчислює ймовірність перемоги зелених;
$so l v e (c, a, b)$ solve(c, a, b) обчислює ймовірність перемоги синіх;

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