Padding
SRM 844 · 2023-01-19 · by misof
Problem Statement
You are selling and shipping tiny marbles. You are currently very happy because you just found a customer who is willing to buy as many as you can ship.
Marbles can be shipped in rectangular boxes of any size. However, the box must first be fitted with soft padding that will prevent the marbles from being damaged in transport. The requirements are the same for boxes of all size: there must be P inches of padding on each side of the box (i.e., bottom, top, and all four vertical faces).
You are given the number N of boxes you currently have in your warehouse.
You are also given their dimensions in the
Assume you have a sufficient supply of padding and a sufficient supply of marbles. Calculate and return the total volume (in cubic inches) of space in your boxes that can be filled with marbles.
Constraints
- N will be between 1 and 50, inclusive.
- X, Y, and Z will have exactly N elements each.
- Each element of X, Y, and Z will be between 1 and 100, inclusive.
- P will be between 1 and 10, inclusive.
1
{10}
{20}
{30}
1
Returns: 4032
We have a single 10x20x30 box. The volume of the whole box is 6000 cubic inches, but once we insert the padding along all walls, the remaining space has only 4032 cubic inches.
3
{10, 20, 30}
{20, 10, 10}
{30, 30, 20}
1
Returns: 12096
Three boxes. Each of them is rotated differently but each of them is a 10x20x30 box. As we saw in the previous example, each of them has 4032 cubic inches free after the padding is inserted, so the total volume is 3*4032.
3
{19, 20, 21}
{30, 30, 30}
{30, 30, 30}
10
Returns: 100
The first box cannot be used, we cannot fit the required amount of padding inside. The second box can have the required amount of padding but there will be no empty space left. In the third box, once the walls are padded, the empty space in the middle will have the shape of a 1x10x10 box.
10
{1,2,3,4,5,6,7,8,9,10}
{3,4,5,6,7,8,9,10,1,2}
{5,6,7,8,9,10,1,2,3,4}
1
Returns: 360
10
{1,2,3,4,5,6,7,8,9,10}
{3,4,5,6,7,8,9,10,1,2}
{5,6,7,8,9,10,1,2,3,4}
2
Returns: 63
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Padding with a public method int volume(int N, vector<int> X, vector<int> Y, vector<int> Z, int P) · 50 test cases · 2 s / 256 MB per case