Кидання гральних костей#11753

Кидання гральних костей (Розбір)

Математичне сподівання однієї кості. Кость з $s$ гранями випадає кожною гранню $1, 2, ..., s$ 1, 2, ..., s з ймовірністю $1/ s$ , тому її матсподівання дорівнює середньому арифметичному цих чисел:

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

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

Матсподівання суми дорівнює сумі матсподівань, тому для очок Аліси $A$ і очок Боба $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}

Очки розподілені симетрично відносно матсподівання. На одній кості значення $1$ і $s$ , $2$ і $s - 1$ s - 1 і так далі випадають з однаковою ймовірністю, тобто кость симетрична відносно $(1 + s) /2$ (1 + s) / 2. Сума симетричних величин теж симетрична — відносно свого матсподівання.

Аліса виграє при $E [A] > E [B]$ E[A] > E[B], Боб виграє при $E [A] < E [B]$ E[A] < E[B]. Таким чином:

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.

Для розв'язання задачі достатньо порівняти суми $S A = \sum a_{k} + m$ SA = \sum a_k + m та $S B = \sum b_{k} + n$ SB = \sum b_k + n.

Приклад

У Аліси вісім костей з $4$ гранями, а у Боба одна кость з $6$ гранями. Тоді $S A = 8 \cdot 4 + 8 = 40$ SA = 8 \cdot 4 + 8 = 40 і $S B = 6 + 1 = 7$ SB = 6 + 1 = 7, так що $S A > S B$ SA > SB і відповідь ALICE.

Перевіримо це безпосередньо. Найменша сума, яку може набрати Аліса, дорівнює $8 \cdot 1 = 8$ 8 \cdot 1 = 8, а найбільша сума Боба дорівнює $6$ . Тому Аліса виграє при будь-якому результаті кидків: $p_{a} = 1, p_{b} = 0$ p_a = 1, p_b = 0.

Розглянемо другий тест. У Аліси кості з $6$ і $4$ гранями, у Боба — з $4$ і $6$ гранями. Тоді $S A = 6 + 4 + 2 = 12$ SA = 6 + 4 + 2 = 12 і $S B = 4 + 6 + 2 = 12$ SB = 4 + 6 + 2 = 12, так що $S A = S B$ SA = SB і відповідь TIED.

Це видно і без обчислень: у Аліси і Боба однакові набори костей, відрізняється лише порядок їх запису. Тому їхні очки розподілені однаково, і $p_{a} = p_{b}$ p_a = p_b.

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

Зчитуємо вхідні дані. Суму $\sum a_{k} + m$ \sum a_k + m накопичуємо у змінній $s A$ , а суму $\sum b_{k} + n$ \sum b_k + n накопичуємо у змінній $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++

Порівнюємо суми і виводимо відповідь.

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