1276 - Going to the movies
Time Limit : 4 Second
Memory Limit : 128 MB
Submission: 15
Solved: 9
- Description
- 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, the movie already started. The usher standing at the door agreed to let them in one by one. Each of the girls 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 just sits down. If it is already taken, she continues to walk in the same direction until she finds the first free seat, and sits there.
Of course, it is possible that some unfortunate girl will reach the end of the row without finding a place to sit. In that case, the usher comes and throws her out.
Problem specification
You are given the numbers N and K.
Assume that each girl’s ticket had a number between 1 and K, inclusive. Each number was drawn uniformly at random, and draws were independent.
Also assume that the entire row was empty when the first girl started to look for her seat.
Compute the probability that at least one girl suffered the sad fate of being thrown out by the usher.
- Input
- The first line of the input file contains an integer T specifying 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.
0 < N, K <= 10 - 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.)
- sample input
-
3 1 10 2 3 3 3
- sample output
-
0/1 1/9 11/27
- hint
- In the third case there are 3^3 = 27 possibilities. Out 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.
- source
- IPSC 2009