2007 Canadian Computing Competition, Stage 1

Problem S2: Boxes

Nowadays, almost any item can be bought and sold on the internet. The problem is shipping. Before an item can be sent, it must be carefully packaged in a cardboard box to protect it.

While items come in many shapes and sizes, finding a box just the right size can be a problem. If the box is too small, the item will not fit. If the box is unnecessarily big, shipping cost will be higher, and the item is more likely to move around inside the box, and it may break.

Cardboard box manufacturers offer a fixed set of standard box sizes. Your task is to find the standard box size with the smallest volume into which an item will fit.

Each box is a rectangular prism with a given length, width, and height. Each item is also a rectangular prism with a given length, width, and height. An item may be rotated by multiples of 90 degrees in any direction before being packed into a box, but when it is packed, its faces must be parallel to the faces of the box. An item will fit into a box as long as its dimensions are equal to or less than the dimensions of the box.

Input

The first line of input will contain a single integer n; 0 < n < 1000, the number of different sizes of boxes available. The next n lines will contain three integers each, giving the length, width, and height of a box.

The following line will contain a single integer m; 0 < m < 1000, the number of items to be packaged.

The next m lines will contain three integers each, giving the length, width, and height of an item. All dimensions will be in millimetres and in the range from 1 mm to 2000 mm.

Output

Output is to consist of m lines, one for each item in the input. For each item, output a line containing a single integer, the volume (in mm³) of the smallest box into which the item will fit. The same size of box may be reused for any number of items. If an item does not fit in any box, print the line: Item does not fit. (with a period!)

Sample Input

3
1 2 3
2 3 4
3 4 5
5
1 1 1
2 2 2
4 3 2
4 3 3
4 4 4

Sample Output

6
24
24
60
Item does not fit.

All Submissions
Best Solutions

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The sample inputs, as well as two of the two test cases,  work, but I can't figure out how to solve that last three. Any hints?

Thanks in advance

I don't think you are calculating the area properly

What am I not considering? What is wrong with my code(s)?

So you swap the areas, but as for the actual box dimensions...?

THANK YOU! wow lol

I got all the sample inputs right, but I can't get 4 of the test cases right even with unsigned long long int lol...

ty for any hints : )

Read the problem statement more carefully, and consider this, can you fit an item of size 1x1x100 into a 5x5x5 box?