CCC '07 S2 - Boxes

View as PDF

Submit solution

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

Problem type
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 1\,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.


  • 0
    Rhumph  commented on Jan. 13, 2023, 3:17 p.m.

    Can someone have a look at my code and provide a hint. I am failing scenarios 1 and 5. Thanks.

  • 0
    juniorroit  commented on Dec. 31, 2021, 12:32 p.m.

    I keep getting the test case #1,3,5 wrong. Any ideas what I could be doing wrong?

    • 7
      Spitfire720  commented on Dec. 31, 2021, 2:45 p.m. edit 2

      I've looked at your code and I can tell you a few things.

      Your output should match the judge's expected output exactly. That means no newlines before the output, and no trailing whitespaces(mostly). CCC is very strict about how their output should look like.

      Secondly, I see you set some conditions to check if the input is within the given constraints. That's actually unnecessary. The problem does state that n and m are within 0 and 1000, but they say that in the sense that the input will be guaranteed to be within 0 and 1000, and not something you have to look out for.

      Another thing about your code is that you've created a lot of unnecessary stuff in there that could be deleted. For example, if you want to take in dimensions as an integer and a string, you could do this all in one line:

      a = list(map(int, input().split()))

      This line of code will take the line of input, split it by its whitespace, and convert the remaining number strings to integers and store them in a list.

      Finally, although this is not as important as the rest, it's still quite useful to know. You do not have to print out your output all at the end, at least for DMOJ. Therefore, even as you take in input, you can output something and DMOJ will still pass you as long as it's correct. This can save you having to store your output somewhere so you can print it out at the end.

      Hope this helps :)

      • 2
        juniorroit  commented on Jan. 1, 2022, 4:16 a.m.

        thanks a lot for the advice!! But I still don't pass test case #1,3,5. I think there might be a problem with my approach of finding the smallest box for the items. Am I supposed to be indicating the smallest box by determining its volume or am I just wrong?

        And one small question, how do I look at other people's codes? If I try to click on others' codes, it leads me to an error page.

        • 3
          Spitfire720  commented on Jan. 1, 2022, 4:31 a.m.

          This may not solve the whole problem, but one error I'm seeing is that you only check if the first dimension fits, although other dimensions could not fit.

          To check on others' codes, you have to solve the problem yourself, to prevent you from copying off other people's solutions.

          • 3
            juniorroit  commented on Jan. 1, 2022, 8:19 a.m.

            Yep, I solved it. Turns out I was overthinking the question. Thank you so much for the help btw