Would anyone please give me a explanation on 312B - Archer ???
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Would anyone please give me a explanation on 312B - Archer ???
Название |
---|
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.
Got it... Thanks for nice explanation... :)
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)].
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...