Problems
Bleatrix Trotter is a sheep who lives in a two-dimensional field that is an infinite grid of unit cells. Her home is in a unit cell that we denote as (0, 0) — that is, all coordinates are given relative to Bleatrix's home cell. However, because she has been sleepwalking, she is currently in the unit cell at the coordinates (X, Y) — that is, in a cell X columns east of, and Y rows north of, her home cell. The two sheepdogs who have been assigned to protect Bleatrix have just noticed that she is missing, and now they want to herd her back to her home cell.
Before each of Bleatrix's moves, the two sheepdogs can move to any grid cells that they want, except that they cannot both move to the same cell, and neither one can move to Bleatrix's current cell. Once the sheepdogs are in place, Bleatrix, who is sleepwalking, will make a random unit move in a direction that would not take her into a cell with a sheepdog. That is, she takes the set of four possible unit moves (north, south, west, east), discards any that would move her into a cell with a sheepdog, and then chooses uniformly at random from the remaining moves. Then the sheepdogs can position themselves again, and so on (notice that, unlike Bleatrix, the sheepdogs do not have to make unit moves).
Once Bleatrix arrives at her home at (0, 0), she stops sleepwalking, wakes up, and grazes peacefully, and does not make any more moves thereafter.
If the sheepdogs coordinate their movements to minimize the expected number of Bleatrix's moves to reach her home, what is that expected number?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each case consists of one line with two integers X and Y, representing the coordinates of Bleatrix's starting cell, as described above.
Output
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is the expected number of Bleatrix's moves, as described above.
y will be considered correct if it is within an absolute or
relative error of 10-6 of the correct answer. See the Competing
section of the
FAQ
for an explanation of what that means, and what formats of real numbers we
accept.
Example
1
-1 1
Case #1: 4.000000
You must sign in to write code.