107 - ZOJ Monthly, July 2011 - D
A man is lost in a strange world. In this world, he is a human in the daytime, and he will become a pig at night. The strange world is rectangle which is seperated into many 1 * 1 grids, from (0,0) to (X,Y). Every grid has a coordinate ( x , y ). If he is in the grid ( x , y ), he can jump to grid ( x - k * y , y ) or ( x , y - k * x ). k is a positive integer. For example, if he is in the grid (4,9), he can only jump to the grid (4,1) or (4,5). At night, he jumps to another grid at 1:00 AM as pig. In the daytime, he jumps to another grid at 1:00 PM as a human. So he will jump exactly twice everyday.
As the figure show, the grids ( x , 0 ), ( 0 , y ) (0 <= x <= X, 0 <= y <= Y ) are the river. When he Jump into the river, he will change from pig to human or change from human to pig immediately. And his property will never change from then on. It means that if he jump into the river in the daytime, he will be a pig forever. He want to jump into the river at night, so that he change from pig to human immediately, and can be a human forever, never become a pig again.
When he become a pig at night, he will jump to a grid whose coordinate satisfies ( x - k * y , y ) or ( x , y - k * x ) arbitrarily. He will not jump out of the strange world either in the daytime or at night. At the beginning, he is at the grid ( x0 , y0 ). To ensure that he can jump into the river as a pig at last, at the beginning, he can choose to start as a pig at night or as a human in the daytime. You need to determine what time (day or night) to start in every grid of the strange world excecpt the river. Use a matrix to display it.
There are multiple cases (no more than 100).
Each case contain two integers X and Y (1 <= X * Y <= 40000) indicating the size of the strange world.
For each test case i, print case number in the form "Case #i" in one single line. And there is a X*Y matrix. The j th charater of the i th line indicating what time (day or night) to start in the grid ( i , j ). 'H' means that to ensure that he can jump into the river as a human, he needs to start as a human in the daytime. 'P' means that to ensure that he can jump into the river as a human, he needs to start as a pig at night.
1 2 2 3
Case #1: PH Case #2: PHH HPP
Author: LIANG, Jiaxing
Contest: ZOJ Monthly, July 2011