Il lancio dei dadi#11753

Il lancio dei dadi (Editoriale)

Valore atteso di un dado. Un dado con $s$ facce mostra ciascuna faccia $1, 2, ..., s$ 1, 2, ..., s con probabilità $1/ s$ , quindi il suo valore atteso è uguale alla media aritmetica di questi numeri:

E = \frac{1 + 2 + ... + s}{s} = \frac{1 + s}{2} .

E = \frac{1 + 2 + ... + s}{s} = \frac{1+s}{2}.

Il valore atteso di una somma è uguale alla somma dei valori attesi, quindi per i punti di Alice $A$ e i punti di Bob $B$

E [A] = \frac{( a _{1} + 1 ) + ... + ( a _{m} + 1 )}{2}, E [B] = \frac{( b _{1} + 1 ) + ... + ( b _{n} + 1 )}{2}

E[A] = \frac{(a_1 + 1)+ ... + (a_m + 1)}{2},~~~E[B] = \frac{(b_1 + 1) + ... + (b_n + 1)}{2}

I punti sono distribuiti simmetricamente rispetto al valore atteso. Su un singolo dado, i valori $1$ e $s$ , $2$ e $s - 1$ s - 1 e così via compaiono con la stessa probabilità, cioè il dado è simmetrico rispetto a $(1 + s) /2$ (1 + s) / 2. La somma di variabili simmetriche è anch'essa simmetrica — rispetto al proprio valore atteso.

Alice vince quando $E [A] > E [B]$ E[A] > E[B], Bob vince quando $E [A] < E [B]$ E[A] < E[B]. Quindi:

p_{a} > p_{b} \Leftrightarrow E [A] > E [B] \Leftrightarrow a_{1} + a_{2} + ... + a_{m} + m > b_{1} + b_{2} + ... + b_{n} + n .

p_a > p_b ⇔ E[A] > E[B] ⇔ \\ a_1 + a_2 + ... + a_m + m > b_1 + b_2 + ... +b_n + n.

Per risolvere il problema è sufficiente confrontare le somme $S A = \sum a_{k} + m$ SA = \sum a_k + m e $S B = \sum b_{k} + n$ SB = \sum b_k + n.

Esempio

Alice ha otto dadi con $4$ facce, mentre Bob ha un dado con $6$ facce. Allora $S A = 8 \cdot 4 + 8 = 40$ SA = 8 \cdot 4 + 8 = 40 e $S B = 6 + 1 = 7$ SB = 6 + 1 = 7, quindi $S A > S B$ SA > SB e la risposta è ALICE.

Verifichiamolo direttamente. La somma minima che Alice può ottenere è $8 \cdot 1 = 8$ 8 \cdot 1 = 8, mentre la somma massima di Bob è $6$ . Perciò Alice vince indipendentemente dal risultato dei lanci: $p_{a} = 1, p_{b} = 0$ p_a = 1, p_b = 0.

Consideriamo il secondo test. Alice ha dadi con $6$ e $4$ facce, Bob ha dadi con $4$ e $6$ facce. Allora $S A = 6 + 4 + 2 = 12$ SA = 6 + 4 + 2 = 12 e $S B = 4 + 6 + 2 = 12$ SB = 4 + 6 + 2 = 12, quindi $S A = S B$ SA = SB e la risposta è TIED.

Questo si vede anche senza calcoli: Alice e Bob hanno gli stessi insiemi di dadi, cambia solo l'ordine in cui vengono elencati. Perciò i loro punteggi sono distribuiti allo stesso modo, e $p_{a} = p_{b}$ p_a = p_b.

Implementazione dell'algoritmo

Leggiamo i dati di input. Accumuliamo la somma $\sum a_{k} + m$ \sum a_k + m nella variabile $s A$ , e la somma $\sum b_{k} + n$ \sum b_k + n nella variabile $s B$ .

scanf("%d %d", &m, &n);
sA = m;  sB = n;
for (i = 0; i < m; i++)
{
  scanf("%d", &x);
  sA += x;
}

for (i = 0; i < n; i++)
{
  scanf("%d", &x);
  sB += x;
}

C++

Confrontiamo le somme e stampiamo la risposta.

if (sA > sB)
  puts("ALICE");
else if (sA < sB)
  puts("BOB");
else
  puts("TIED");