Jackpots#11316

Jackpots (Editoriale)

Immaginiamo che il giocatore abbia estratto subito tutte le palline in ordine casuale, cioè abbiamo ottenuto una permutazione casuale di $n = a + b + c$ n = a + b + c palline. Il gioco termina quando per la prima volta finisce un colore. Quindi vince il colore la cui ultima pallina si trova nella permutazione prima di tutte le altre.

Calcoliamo la probabilità del jackpot d'oro (rosso). Affinché il rosso vinca, l'ultima pallina della fila deve essere verde o blu. Analizziamo entrambi i casi.

Caso A: La probabilità che l'ultima pallina della fila sia verde è uguale a $b / n$ (le palline verdi sono $b$ su $n$ ). Il verde ha perso. Restano il rosso e il blu, e bisogna capire chi di loro vincerà.

Immaginiamo mentalmente di togliere le palline verdi dalla fila e guardiamo solo le palline rosse e blu (ce ne sono $a + c$ a + c). Il rosso vince se l'ultima tra le palline rosse e blu è blu. La probabilità che l'ultima tra $a + c$ a + c palline sia blu è uguale a $c / (a + c)$ c / (a + c). Ciascuna di queste palline può risultare l'ultima con uguale probabilità, e tra esse ci sono $c$ palline blu.

La probabilità del Caso $A$ è uguale a $\frac{b}{n} \cdot \frac{c}{a + c}$ \frac{b}{n} \cdot \frac{c}{a+c}.

Caso B: La probabilità che l'ultima pallina della fila sia blu è uguale a $c / n$ (le palline blu sono $c$ su $n$ ). Il blu ha perso. Togliamo le palline blu e guardiamo le palline rosse e verdi (ce ne sono $a + b$ a + b). Il rosso vince se tra loro l'ultima risulta verde, questa probabilità è uguale a $b / (a + b)$ b / (a + b).

La probabilità del Caso $B$ è uguale a $\frac{c}{n} \cdot \frac{b}{a + b}$ \frac{c}{n} \cdot \frac{b}{a+b}.

I casi $A$ e $B$ non si intersecano (l'ultima pallina non può essere contemporaneamente verde e blu), quindi la probabilità di vittoria del rosso sarà

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}

Analogamente, la probabilità di vittoria del verde è uguale a

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}

La probabilità di vittoria del blu è uguale a

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}

Esempio

Consideriamo il secondo test ( $a = 1, b = 2, c = 3, n = a + b + c = 6$ a = 1, b = 2, c = 3, n = a + b + c = 6). Calcoliamo le probabilità di vincita dei jackpot:

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}

Implementazione dell'algoritmo

La funzione gcd calcola il massimo comun divisore dei numeri $a$ e $b$ .

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

La funzione solve calcola la probabilità di vittoria del rosso.

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

Parte principale del programma. Leggiamo i dati di input.

cin >> a >> b >> c;

Calcoliamo e stampiamo la risposta. Notiamo che la chiamata della funzione:

$so l v e (a, b, c)$ solve(a, b, c) calcola la probabilità di vittoria del rosso;
$so l v e (b, c, a)$ solve(b, c, a) calcola la probabilità di vittoria del verde;
$so l v e (c, a, b)$ solve(c, a, b) calcola la probabilità di vittoria del blu;

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