2005 ASIA PROGRAMMING CONTEST – MANILA

October 29, 2005

 

Problem E

 

Mayday! Mayday!

 

Input File:  e.in

 

In some distant future, the human race had charted the space for exploration. A three dimensional (3D) coordinate system (x, y, z) had been developed to identify a specific location in space. Each coordinate value is represented by a very long integer ranging from -2⁴⁰  to +2⁴⁰ .

 

The Earth Command Center (ECC) sent you to explore a 3D space that is several light years away. Upon reaching the area, you started your exploration, gathering critical information of the area. Several days had passed without incident. Suddenly, your system picked up a strange erratic signal indicating high cosmic activity. Without warning, your ship was hit by a cosmic flare hitting your ship. With your quick reaction, you were able activate your cosmic shield saving everyone inside the ship, but the impact knocked off the engine and communication systems. Still within the area of exploration, your ship is motionless with only a few months of food supply left.

 

Checking out in detail your communication system, you figured out that you have one chance of sending a 3-byte data to the ECC. Glancing at your navigation panel, you can still read your current ship’s position in (x, y, z) coordinate system. Unfortunately, this is too long to compress into 3 bytes. Knowing that you are still in the assigned area of space exploration by the ECC, you recalled your glory days in spatial coding, where you can code a 3D area by dividing the 3D space into 8 equal cubes known as octant. These octants are then assigned a number from 0 to 7 (using only 3 bits each) as shown in Figure 1.

Figure 1: (a) Shows the axis values of the coordinate system; (b) Shows the division of a 3D space into 8 cubes/octants with its corresponding numeric label

Octant 6 is behind Octant 4 and below Octant 2

 

           

This process of division can be applied recursively on each octant in order to code a smaller 3D space. If the ship’s coordinates fall exactly on the boundary of two or more octants, it is said to belong to the octant with the lower code value. Given 3 bytes, you can perform the recursive division 8 times coding the 3D space that your ship is located and sending this to ECC for a search and rescue.

 

Input

 

The input will contain several test cases. The first line will indicate the number of test cases. Each test case is composed of 3 sets of x, y, z coordinates, namely top-left-front, bottom-right-rear and your ship’s position.

 

Output

 

The output is a 3 byte code representing the code of the 3D space containing your ship.

 

For this problem, all numbers are displayed in hexadecimal format.

 

 

 

Input	Output
2 +A000000000 +A000000000 +A000000000 +FF00000000 +FF00000000 +FF00000000 +A000000001 +A000000001 +A000000001 +A000000000 +A000000000 +A000000000 +FF00000000 +FF00000000 +FF00000000 +FEEEEEEEEE +FEEEEEEEEE +FEEEEEEEEE	Case 1: 000000 Case 2: FFFFFF