Expected Result

Limits 1s, 256 MB

A witch has imprisoned Bob in the 1st room of the Central Witchland Hotel. The hotel is weird. All the rooms are numbered linearly, i.e. 1, 2, 3,….., n, n + 1, … and so on. Those rooms have no doors or windows except the rooms which have a room number greater than n. From the rooms having a room number greater than n, Bob can get out of the hotel. That means Bob has no way to get out of the hotel without reaching a room which has doors or windows.Luckily, Bob has found a device that generates a number M from 0 to K – 1 with equal probability and it will teleport Bob to the Mth room from the current room. This means if Bob is currently in Xth room and the device generates M, then he will be teleported to the (X + M)th room. You have to determine what is the expected number of times he has to use that device to get out of the hotel.

This is a companion discussion topic for the original entry at https://toph.co/p/expected-result