Choosing The Box
All submissions for this problem are available.
John’s machine manufacturing company gets failed ( even your program could not save him !! ) so he starts a new box business. He has many boxes left from his previous business. He has exactly M boxes each of which could be denoted by its 3 dimensions – (X,Y,Z). He has been given an order according to which he needs to deliver N identical boxes to keep N objects of some given dimension. Dimension of the object will be again of the form – (X,Y,Z). You may assume that an object of size (X, Y, Z) would ﬁt perfectly into a box of size (X,Y,Z). If there are not at least N boxes that ﬁt perfectly, then John wants N boxes that ﬁt the items as tightly as possible. The box size that ﬁts the items as tightly as possible is the one which minimizes the empty space when the item is put inside the box. An item can be rotated in any direction to be accommodated inside a box; therefore, a box of size(X, Y, Z) is as good as a box of size (Y, Z, X), for example.
The first line would give the number of test cases.
The ﬁrst line of a test case contains two integers N and M, indicating respectively the number of boxes the client orders (1 ≤ N ≤ 1500) and the number of boxes John has (1 ≤ M ≤ 1500). The second line contains three integers X, Y and Z, representing the dimensions of the item the client wants to wrap (0 < X, Y, Z ≤ 50). Each of the next M lines contains three integers A, B and C representing the dimensions of a box in the stock list (0 < A, B, C ≤ 50).
Repeat for next test case.
For each test case in the input your program must produce one line, containing either :
- The single word ‘impossible’, in case it is not possible to fulﬁll the client’s order (because there are not at least N boxes of the same size in stock that can contain the item).
- one integer V , which speciﬁes the volume of empty space left when one of the N items packed in one of the boxes chosen.
Input: 3 1 1 2 4 3 2 3 4 2 6 3 1 3 7 4 7 10 8 2 2 8 10 6 2 9 7 7 4 6 2 9 1 1 3 3 3 1 1 1 Output: 0 99 impossible
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.