BoxFilling | Topcoder Archive

Problem Statement

We have a box that consists of (sizeX x sizeY x sizeZ) = N unit cubes. These cubes have coordinates ranging from (1,1,1) to (sizeX,sizeY,sizeZ).

We want to number the unit cubes, using integers from 1 to N. We will do this algorithmically.

We will call a box "1-dimensional (1D)" if at least two of its dimensions are 1, "2-dimensional (2D)" if exactly one of its dimensions is 1, and "3-dimensional (3D)" otherwise.

The algorithm used to number a 1-dimensional box is simple: order the cubes according to the sums of their coordinates (in ascending order), and number them in this order.

To number a 2-dimensional box, we follow this algorithm:

If X size is greater than 1, consider all cubes with both Y and Z coordinates minimal, number them as a 1D box, and throw them away.
If we still have a 2D box, if Y size is greater than 1, consider all cubes with both X and Z coordinates minimal, number them as a 1D box, and throw them away.
If we still have a 2D box, if Z size is greater than 1, consider all cubes with both X and Y coordinates minimal, number them as a 1D box, and throw them away.
Recursively number the rest of the box.

For example, a 4x5x1 box filled using this algorithm looks as follows:

z=1
   x:1  2  3  4
 y:+--+--+--+--+
  1| 1| 2| 3| 4|
   +--+--+--+--+
  2| 5| 9|10|11|
   +--+--+--+--+
  3| 6|12|15|16|
   +--+--+--+--+
  4| 7|13|17|19|
   +--+--+--+--+
  5| 8|14|18|20|
   +--+--+--+--+

To number a 3-dimensional box, we follow this algorithm:

Consider all cubes with the Z coordinate minimal, number them as a 2D box, and throw them away.
If we still have a 3D box, consider all cubes with the Y coordinate minimal, number them as a 2D box, and throw them away.
If we still have a 3D box, consider all cubes with the X coordinate minimal, number them as a 2D box, and throw them away.
Recursively number the rest of the box.

For example, a 4x3x3 box filled using this algorithm looks as follows:

z=1
   x:1  2  3  4
 y:+--+--+--+--+
  1| 1| 2| 3| 4|
   +--+--+--+--+
  2| 5| 7| 8| 9|
   +--+--+--+--+
  3| 6|10|11|12|
   +--+--+--+--+

z=2
   x:1  2  3  4
 y:+--+--+--+--+
  1|13|14|15|16|
   +--+--+--+--+
  2|21|25|26|27|
   +--+--+--+--+
  3|22|28|29|30|
   +--+--+--+--+

z=3
   x:1  2  3  4
 y:+--+--+--+--+
  1|17|18|19|20|
   +--+--+--+--+
  2|23|31|32|33|
   +--+--+--+--+
  3|24|34|35|36|
   +--+--+--+--+

You will be given the box dimensions sizeX, sizeY, and sizeZ, and the coordinates of a single cube (cubeX,cubeY,cubeZ). Write a method that will compute the number assigned to the cube at the given coordinates, when using the algorithm described above.

Definition

Class:: BoxFilling
Method:: getNumber
Parameters:: int, int, int, int, int, int
Returns:: long
Method signature:: long getNumber(int sizeX, int sizeY, int sizeZ, int cubeX, int cubeY, int cubeZ)
(be sure your method is public)

Notes

Note that the box described by sizeX, sizeY, and sizeZ is not necessarily a 3D box.

Constraints

sizeX, sizeY and sizeZ will be between 1 and 109, inclusive.
The volume of the box will not exceed 1018.
cubeX will be between 1 and sizeX, inclusive.
cubeY will be between 1 and sizeY, inclusive.
cubeZ will be between 1 and sizeZ, inclusive.

Examples

```
4
```
```
5
```
```
1
```
```
2
```
```
4
```
```
1
```
```
Returns: 13
```
This is the box from the first example in the problem statement.
```
4
```
```
3
```
```
3
```
```
2
```
```
2
```
```
2
```
```
Returns: 25
```
This is the box from the second example in the problem statement.
```
4
```
```
3
```
```
3
```
```
4
```
```
2
```
```
1
```
```
Returns: 9
```
Same box, different cube coordinates.
```
2
```
```
2
```
```
2
```
```
1
```
```
1
```
```
1
```
```
Returns: 1
```

Returns: 9416237809215

```
3
```
```
1
```
```
10
```
```
3
```
```
1
```
```
2
```
```
Returns: 14
```
```
4
```
```
2
```
```
4
```
```
3
```
```
2
```
```
3
```
```
Returns: 28
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.