Zər atma#11753

Zər atma (Həll təhlili)

Bir zərin riyazi gözləntisi. $s$ üzlü zər $1, 2, ..., s$ 1, 2, ..., s üzlərinin hər birini $1/ s$ ehtimalı ilə göstərir, buna görə onun riyazi gözləntisi bu ədədlərin arifmetik ortasına bərabərdir:

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

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

Cəmin riyazi gözləntisi riyazi gözləntilərin cəminə bərabərdir, buna görə Alisanın xalları $A$ və Bobun xalları $B$ üçün

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}

Xallar riyazi gözləntiyə nəzərən simmetrik paylanıb. Bir zərdə $1$ və $s$ , $2$ və $s - 1$ s - 1 və s. qiymətlər eyni ehtimalla düşür, yəni zər $(1 + s) /2$ (1 + s) / 2 ətrafında simmetrikdir. Simmetrik kəmiyyətlərin cəmi də simmetrikdir — öz riyazi gözləntisinə nəzərən.

Alisa $E [A] > E [B]$ E[A] > E[B] olduqda qalib gəlir, Bob isə $E [A] < E [B]$ E[A] < E[B] olduqda qalib gəlir. Beləliklə:

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.

Məsələni həll etmək üçün $S A = \sum a_{k} + m$ SA = \sum a_k + m və $S B = \sum b_{k} + n$ SB = \sum b_k + n cəmlərini müqayisə etmək kifayətdir.

Misal

Alisanın $4$ üzlü səkkiz zəri var, Bobun isə $6$ üzlü bir zəri var. Onda $S A = 8 \cdot 4 + 8 = 40$ SA = 8 \cdot 4 + 8 = 40 və $S B = 6 + 1 = 7$ SB = 6 + 1 = 7, deməli $S A > S B$ SA > SB və cavab ALICE-dir.

Bunu bilavasitə yoxlayaq. Alisanın toplaya biləcəyi ən kiçik cəm $8 \cdot 1 = 8$ 8 \cdot 1 = 8-dir, Bobun ən böyük cəmi isə $6$ -dır. Buna görə Alisa istənilən nəticədə qalib gəlir: $p_{a} = 1, p_{b} = 0$ p_a = 1, p_b = 0.

İkinci testə baxaq. Alisanın $6$ və $4$ üzlü zərləri var, Bobun isə $4$ və $6$ üzlü zərləri var. Onda $S A = 6 + 4 + 2 = 12$ SA = 6 + 4 + 2 = 12 və $S B = 4 + 6 + 2 = 12$ SB = 4 + 6 + 2 = 12, deməli $S A = S B$ SA = SB və cavab TIED-dir.

Bu, hesablamalar olmadan da görünür: Alisa və Bobun zər dəstləri eynidir, yalnız onların qeyd olunma sırası fərqlidir. Buna görə onların xalları eyni cür paylanıb və $p_{a} = p_{b}$ p_a = p_b.

Alqoritmin realizasiyası

Giriş məlumatlarını oxuyuruq. $\sum a_{k} + m$ \sum a_k + m cəmini $s A$ dəyişənində, $\sum b_{k} + n$ \sum b_k + n cəmini isə $s B$ dəyişənində toplayırıq.

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

Cəmləri müqayisə edib cavabı çap edirik.

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