BoxFilling

TCO08 Round 1 · 2008-01-21 · by Olexiy

TCO08 Round 1 · 2008-01-21 · by Olexiy · Brute Force, Recursion, Simple Math, Simple Search, Iteration, Simulation

Show categories

Class Name: BoxFilling

Return Type: long

Method Name: getNumber

Arg Types: (int, int, int, int, int, int)

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.

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

43633
35453
34533
2344
32442
34221
Returns: 9416237809215

10)

1
1
100000000
1
1
47000000
Returns: 47000000

This is a very tall 1D box.

Submissions are judged against all 128 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BoxFilling with a public method long long getNumber(int sizeX, int sizeY, int sizeZ, int cubeX, int cubeY, int cubeZ) · 128 test cases · 2 s / 256 MB per case