RearrangingBoxes | Topcoder Archive

Problem Statement

The floor of a big warehouse consists of A*B unit square tiles. On each tile there is a tower of H unit cube boxes. All the A*B*H boxes currently form one big cuboid that exactly fills the warehouse.

The manager of the warehouse likes order, so he is pretty happy that the boxes fill the warehouse. Unfortunately for him, K boxes have to be delivered somewhere else, thus only A*B*H - K boxes will remain in the warehouse. The manager wants to have something that will remind him of how nice it was having the full cuboid, so he wonders whether he will be able to rearrange the remaining boxes in such a way that the surface area of the resulted solid will be exactly the same as the surface area of the original cuboid, i.e., 2*(A*B + A*H + B*H).

The boxes must be stacked in such a way that on each tile there is a tower consisting of at most H boxes. (Boxes cannot levitate in the air. Towers of height zero are allowed.) Moreover, the resulting solid must be connected. (Two boxes are directly connected if they share a face; a solid is connected if all pairs of boxes are connected, directly or indirectly.)

If the manager cannot rearrange the boxes according to his wishes, return an empty int[]. Otherwise, imagine the floor of the warehouse as a rectangle with A rows and B columns. Return a int[] of size A*B which contains the heights of towers in the rearranged warehouse, in row major order. If there are multiple solutions, you may return any of them.

Definition

Class:: RearrangingBoxes
Method:: rearrange
Parameters:: int, int, int, long
Returns:: int[]
Method signature:: int[] rearrange(int A, int B, int H, long K)
(be sure your method is public)

Constraints

A and B will be between 1 and 30, inclusive.
H will be between 1 and 10^9, inclusive.
K will be between 1 and A*B*H-1, inclusive.

Examples

```
3
```
```
2
```
```
2
```
```
2
```
```
Returns: {2, 2, 2, 1, 2, 1 }
```
A cuboid of size 3 Ã 2 Ã 2 has surface area of 32. Removing two boxes in the way shown below does not change the surface area. 2 2 2 2 2 2 --> 2 1 2 2 2 1
```
1
```
```
1
```
```
3
```
```
1
```
```
Returns: { }
```
Removing one box from a cuboid of size 1 Ã 1 Ã 3 can only result in a cuboid of size 1 Ã 1 Ã 2 which clearly has a smaller surface area.
```
3
```
```
2
```
```
3
```
```
9
```
```
Returns: { }
```
Another impossible situation. Note that the figure below doesn't show a valid solution, since the solid is not connected: 3 0 0 3 3 0
```
3
```
```
3
```
```
10
```
```
42
```
```
Returns: {0, 10, 0, 10, 8, 10, 0, 10, 0 }
```
10 10 10 0 10 0 10 10 10 --> 10 8 10 10 10 10 0 10 0

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.