Mukit09's blog

Help for Codeforces Round #185(Div.2 B)
By Mukit09, 12 years ago, In English

Would anyone please give me a explanation on 312B - Archer ???

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

This problem have tow simple solutions:

1) We can sum P(win after 1 step) + P(win after 3 step) + ... + P(win after 2 * i + 1 step) + ... = a / b + (1 — a / b) ^ 1 * (1 — c / d) ^ 1 * p + (1 — a / b) ^ 2 * (1 — c / d) ^ 2 * p + ...(1 — a / b) ^ i * (1 — c / d) ^ i * p + ...

Then we use infinite geometric series formula to calculate it.

2) We can assume p as result. So p = P(win after 1 step) + P(win after 3 step) + ... + P(win after 2 * i + 1 step) + ... = P(win after 1 step) + (1 — a / b) * (1 — c / d) * p = a / b + (1 — a / b) * (1 — c / d) * p

p = (a / b) / (1 — (1 — a / b) * (1 — c / d))

Solution.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's denote a/b=p, c/d=r. A turn is the number of SmallR's shot.

The probability of SmallR winning in the first turn is p. The probability of winning in the 2nd turn is (1-p)(1-r)p, because it involves both missing on the 1st turn and SmallR hitting on the 2nd. Similarly, the probability of SmallR winning in the k-th turn is p[(1-p)(1-r)]^(k-1), because the first k turns both of them miss and then SmallR hits.

Then it's clear that the answer is sum(k=1..infty){p[(1-p)(1-r)]^(k-1)}, which is just p times a sum of a geometric series, with the answer p/[1-(1-p)(1-r)].

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks a lot... It's clear to me now...

    because it involves both missing on the 1st turn and SmallR hitting on the 2nd.

    This is the key... Thanks again...

    → Reply