DIXIE003 - Packing Boxes

You just got a job with Amazon! Unfortunately, on your first day of work, you discover that you were hired to pack boxes in one of their warehouses instead of programming their cloud computing engine like you had hoped.

You decide that any job is better than no job, so you set to work. You take your place next to a conveyor belt, where items that customers have purchased travel down the line to you. Your job is to pack each item in a box, then hand it off to someone else to label it and send it to UPS for delivery.

The items that you pack come in all sizes, and you are required to pack each one in the smallest box that it will fit in. You are given a list of box sizes (length, width, and height in inches), and a list of items to pack (again, you are given the length, width, and height for each).

For each item, you must find the smallest box that is big enough to fit the item. You can rotate the item to make it fit, but only at right angles, i.e., you may not stuff an item diagonally into a box.

The list of box sizes is not given in any particular order. You must order them from smallest to largest yourself according to total surface area.

Note: The symbol in the examples below represents a new-line character.

Input

The input is given in the format outlined below.

numberOfBoxSizes
length width height
length width height
etc...
numberOfItems
length width height
length width height
etc...

Output

The output should be one line per item. Each line should give the size of the item followed by the size of the box you will pack it in. Each size should be given exactly as it was provided in the input.

Sample Input

3
5 7 2.5
9 12 3
11.5 17.5 4
5
6 6 2.3
7 1 4.3
3.2 10.3 8.6
1 1.1 1
2.5 7 5

Sample Output

6 6 2.3 9 12 3
7 1 4.3 5 7 2.5
3.2 10.3 8.6 11.5 17.5 4
1 1.1 1 5 7 2.5
2.5 7 5 5 7 2.5


Added by:Dixie State University
Date:2013-03-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Problem from the DSU 2013 ACM Contest

hide comments
2023-03-17 14:31:36 Simes
What is the magic to getting AC here? I've tried outputting the original box and item config line as is, trimming leading and trailing spaces, and removing all double spaces. Every config line seems to have three numbers, and I've checked for tabs and duplicate box sizes in the input - there are none. What have I missed?
2018-06-27 05:57:54
Input contains multiple whitespaces or some other noise. Had to store and print entire lines rather than take numbers as separate floats and reformat them on output as that gives WA.
2013-03-30 17:00:41 Francky
It is said "the smallest box", but you don't give the rule for choosing such a box. It's true, further, you said 'should' for total area as comparison function, but, it should be 'must' isn't it ?
I think description is unclear without that. Please fix it.
(edit : AC with that, but you should/must fix it ;-).
I think this problem belongs (as others) to tutorial section. Any other comments about that ?

(edit: DSU) I will move it to tutorial.

Last edit: 2013-03-30 16:57:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.