|
D |
Puzzles
of Triangles Input: Standard Input Output: Standard Output |
|
Puzzles with geometric shapes are very interesting and is
said to have great impact in developing geometric insight of a child. ACM (Actual
Challenge Makers) is planning to bring out one such puzzle. The specialty of
this puzzle is that all the pieces of this puzzle have the shape of
right-angled triangles. All these right angled pieces make the target
rectangular shape and it is shown in figure 2.
It may be a bit difficult to construct or even reconstruct
a puzzle which is only composed of pieces with the shape of a right-angled
triangle. However if the actual rectangular puzzle is divided into several
square sub-regions, and then those sub-regions are divided into four
right-angled pieces then such puzzles are easy to make and solve.
|
|
|
|
Figure 1: A cut to make four right angled triangle
shaped pieces. |
Figure 2: A conventional puzzle of triangles. |
Whether a rectangle can be divided into small pieces of
squares can itself be an interesting task to solve. But that is not the problem
you have to solve here. Your job is to decide whether a square shaped sheet can
be divided into four right-angled triangles as shown in figure 1. The machine
that is used to cut the pieces can only deal with integers. So the length of
the square shaped sheets is always expressed in integer units and also cutter
can only cut in a straight line from one integer coordinate to another. The
cutting must start on one of the corners of the square shaped sheet, continue
cutting in a triangular path (Like AEF showed in Figure 1) and again finish at
the corner it started. And if four corners of the square sheet are lattice
points (0,0), (N,0), (N,N) and (0,N), where N is the length of sides of the
square shaped sheet then point E and F should also be lattice points. So given
a sheet, you have to determine whether such cuts are possible, and if it is
possible then in how many ways.
Input
The input file contains at most 800 lines of inputs.
Each line
contains an integer N (0<N<1014), which means that we have to
cut an (NxN) sheet.
Input is
terminated by a line containing a single zero. This zero should not be
processed.
Output
For each line of input produce one line of output. This
line contains the serial of output followed by a string or an integer. If it is
not possible to cut the (NxN) sheet in the prescribed way, then print a line “Impossible”, otherwise print an integer W.
Here W denotes the number of ways such a cut is possible. Look at the output
for sample input for details
Sample Input Output for Sample
Input
|
10 20 100 32 0 |
Case 1:
Impossible Case 2: 8 Case 3: 72 Case 4: 24 |
Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman