Problem B
A Bee Love Story
Input: Standard
Input
Output: Standard
Output
Jolly Bee, one of the inhabitants of the Bee world, is about to propose his love, Emily Bee. As he loves Emily Bee very much, he wants to make the proposal very special. He thought all day and night but couldn’t find anything that makes his idea special.
So, he became very sad and decided to fly the Bee garden to find something special. The Bee world can be represented as a hexagonal grid, and each of the cells has a unique id as the picture below.
Two cells are adjacent if they share a side. So, 7 and 6 are adjacent, so are 42 and 22. A Bee garden is a 3-layer cell-collection such that there is a cell in the center and all the other cells are no more than 2 units away from the center cell. Some examples of Bee gardens are given below.
Now J-Bee (Jolly Bee) is wandering around in a Bee garden. Suddenly he found some interesting facts in the garden. He saw that, in each cell of the garden there is a flower petal except the one he is in. Since a garden consists of 19 cells, he found 18 flower petals in the garden. And each of the petals is different (in size, color). He marked each petal with a distinct letter from [b to s]. And he marked his position with 'a'. From the initial petal positions, he wants to rearrange the petals like the following picture.
The reason behind the rearrangement of the petals is that, he wants to escort E-Bee (Emily Bee) through 'a', 'b', 'c', ..., 's' and they will experience the beauty of the precious flower petals in such a nice pattern. And after that he will propose E-Bee.
J-Bee can only move to one of his adjacent cells and in each move he can bring the petal to his cell, and then he goes to the cell where the petal was before. For example, for the given initial petal positions, he can move to one of the three adjacent cells. The possible moves are given below.
Now J-Bee wants to rearrange the petals using his moving techniques. But he doesn’t want to work too hard. So, he wants to make the arrangement in minimum number of moves. Since the petals are too heavy for J-Bee, he can’t use more than 20 moves. Now he is seeking your help to know whether his idea can be implemented or not.
Input
The first line will contain an integer T (T<= 500) denoting the number of cases.
Each case contains 19 integers in a line separated by spaces. The first integer denotes the position of J-Bee in the garden, the next 18 integers will denote the positions of the petals from 'b' to 's' respectively. You can safely assume that all the given positions are taken from a Bee garden satisfying the given restrictions. All the integers will be in the range [0, 109].
Output
For each case print the case number first. After that print one of the following
"Impossible." if the petals can’t be arranged with in infinite number of moves.
"Not possible with in 20 move(s)." if the petals can’t be arranged with in 20 moves, but can be arranged using more than 20 moves.
"Possible with x move(s)." if the petals can be arranged with in x moves, where x is as small as possible and x is not greater than 20.
Sample
Input
|
3 |
Output
for Sample Input
|
Case 1: Possible with 3 move(s). |
Problemsetter: Jane Alam Jan
Special Thanks to: Md. Arifuzzaman Arif