Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Expected Result

By moshiur_cse15 · 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.


The first line of the input will contain an integer, T, number of test cases to follow. Each of the next T lines will continue two integer numbers, n and k, as discussed before.
1 ≤ T ≤ 105
1 ≤ n ≤ 106
2 ≤ K ≤ 10


Print T lines, answer to each test case. Your solution will be considered correct if the absolute difference between your answer and the judge's answer is less than 10-6.


1 3

You have to go to any room numbered greater than n, not in n.
If that device generates 0, he'll stay in the same room.



45% Solution Ratio

tanimahossainEarliest, Oct '19

solaimanopeFastest, 0.1s

solaimanopeLightest, 1.7 MB

shegufaShortest, 716B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.