CCC '07 S2 - Boxes

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2007 Stage 1, Senior #2

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 Specification

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 \operatorname{mm} to 2\,000 \operatorname{mm}.

Output Specification

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 \operatorname{mm}^3) 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.

Sample Input

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

Output for Sample Input

Item does not fit.


  • 1
    println_hi_  commented on Nov. 12, 2016, 9:55 a.m. edit 2

    My program is throwing an error when I try to read the (n+2)'th line of input and assign it to an integer. My code works fine for me on my machine and line n+2 should definitely be an integer. Would it b e possible for someone to explain my problem? EDIT:Thank you:)

    • 1
      Kirito  commented on Nov. 12, 2016, 10:46 a.m. edit 2

      EDIT: Fixed.

  • 2
    Zezima  commented on Oct. 12, 2015, 12:00 p.m.

    It might be a problem with my computer, but for some reason, when I scroll down the page, a black bar appears to the side of the Output for Sample Input. It doesn't appear for the Input, so is it supposed to be there?

    • 1
      Xyene  commented on Oct. 12, 2015, 10:46 p.m.

      It might be an issue with the Flash movie used for the Copy buttons. If the issue persists, please file a bug at our issue tracker.