G – The Game
A
simple game, called KillHer-I, is investigated in Shiraz University game design
group. This game involves two players, each with one piece, and is played on a
board of n squares arranged in a line with a fair dice of m numbers (1, 2, 3,
…, m). Initially, the two pieces are in squares on either ends of the board. The
players take turns to
move their pieces forward by the number of squares indicated by the dice roll. The player who
completes their move in the square already occupied by the opponent's piece,
captures it and wins the game. Otherwise, if a player overpasses their
opponent's piece in their move, they lose. The game continues until one of the
players wins (or the other one loses).
This
game's primary vice is that the whole game is completely decided by chance.
Therefore, another version of this game is designed, called KillHer-II. In this
variant, each player may choose to move their piece from 1 to throw-of-the-dice
squares.
The
designers want to know, the probability of the starting player winning the games
KillHer-I and KillHer-II independently, given the board size n and dice sides
m.
Input
The
first line of input contains an integer T≤200 as the
number of test-cases. Each of the following T lines feature two integers n and
m both less than 100,000.
Output
For
each test-case, you should print on a new line, the probability of the starting
player winning first in KillHer-I and then in KillHer-II, separated by one
space. Each probability should be expressed in exactly 4 decimal places.
|
Sample
Input |
Sample
Output |
|||||||||||||
|
|