Going to the movies
Time limit1sMemory limit1024 MB
Given N girls and K seats with random tickets, find the probability that at least one girl is thrown out, as a reduced fraction.
- Level
Medium6 of 10
- Topics
- Math, Combinatorics
- Solved
- No attempts yet
Problem
N friends decided to go to the local cinema together. They all bought tickets to the same row. As there was still some time left, each of them took her ticket and went shopping until the movie starts.
They all arrived back late, and the movie had already started. The usher standing at the door agreed to let them in one by one. Each girl was supposed to find her place and sit down.
However, the machine that printed their tickets was broken. Instead of consecutive numbers, each girl received a random seat number between 1 and K, where K is the number of seats in their row. The seat numbers they received were not necessarily distinct.
When a girl tries to sit down, she enters the row at the end where seat number 1 is, and walks until she reaches the number on her ticket. If her desired seat is free, she sits down. If it is already taken, she keeps walking in the same direction until she finds the first free seat, and sits there.
Some unlucky girl may reach the end of the row without finding a place to sit. In that case, the usher throws her out.
You are given N and K.
Assume that each girl's ticket has a number between 1 and K, inclusive. Each number is drawn uniformly at random, and the draws are independent.
Also assume that the entire row is empty when the first girl starts to look for her seat.
Compute the probability that at least one girl is thrown out by the usher.
Input
The first line of the input contains an integer T, the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a single line containing two integers N and K.
Output
For each test case, output a single line with the probability as a simplest fraction. Do not output any spaces before or after the / sign.
Constraints
1 ≤ T ≤ 100
Hint
In the third case there are possibilities. Of these, in 11 some girl is thrown out. These 11 sequences are: 133, 222, 223, 232, 233, 313, 322, 323, 331, 332, and 333.
For example, if the sequence is 322, the first girl sits at seat 3, and the second one sits at seat 2. The third one tries to sit at seat 2, finds seats 2 and 3 occupied, and is thrown out.