ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1677. Monkey at the Keyboard

What does it mean?(Что это означает)
Posted by daminus 1 Mar 2012 16:16
I don't understand!!! How given (2, aa) answer is 6. I think that must be 4!!!  Please help, who know that!!!!! (Я не понел Как 2 и аа могут дать ответ 6 Я думаю что должно быть 4 Помогите------------)
Re: What does it mean?(Что это означает)
Posted by lxn 22 Jan 2018 15:37
expected time is inifinite sum of time * p(time), where p(time) is the probability to get resulting string exactly in 'time' steps.
for aa:
probability to get 'aa' in exactly 1 step is 0. (simple)
probability to get 'aa' in exactly 2 steps is 1/4 (simple)
probability to get 'aa' in exactly n steps is probability to get a string of length == n - 1 that ends with 'a', and doesn't contain 'aa' as substring multiplyed by 1/2 (when you have such string there is a 1/2 chance that the next character will be 'a').
for n == 3: 1/8, for n == 4: 1/8 etc.
If you simulate such steps and get a sum for n = [2.. 10000] you will get answer equal to 6

PS.
this is simulation of 10 steps:
0.000000 * 1
0.250000 * 2
0.125000 * 3
0.125000 * 4
0.093750 * 5
0.078125 * 6
0.062500 * 7
0.050781 * 8
0.041016 * 9
0.033203 * 10