I am learning magic tricks to impress my girlfriend Alice. My latest trick is a probabilistic
one, i.e., it does work in most cases, but not in every case. To perform the trick, I first
shuffle a set of many playing cards and put them all in one line with faces up on the table.
Then, Alice secretly selects one of the first ten cards (i.e., she chooses
x0, a secret number between 1 and 10 inclusive) and skips cards
repeatedly as follows: after having selected a card at position xi with a
number c(xi) on its face, she will select the card at position
xi+1 = xi + c(xi).
Alice stops this procedure as soon as there is no card at position xi + c(xi). I then perform the same procedure from a randomly selected starting position that may be different from the position selected by Alice. It turns out that often, I end up at the same position. Alice is very impressed by this trick.
However, I am more interested in the underlying math. Given my randomly selected starting
position and the card faces of every selected card (including my final one), can you compute
the probability that Alice chose a starting position ending up on the same final card? You
may assume that her starting position is randomly chosen with uniform probability (between 1
and 10 inclusive). I forgot to note the cards that I skipped, so these cards are unknown. You
may assume that the card face of every single of the unknown cards is independent of the
other card faces and random with uniform probability out of the possible card faces (i.e.,
For each test case, there are two lines of input:
For each test case, print one line containing the probability that Alice chooses a starting position that leads to the same final card. Your output should have an absolute error of at most 10–7.
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|