Statistics

Problem Statement for "Giftwrap"

Problem Statement

NOTE: for those using plugins to read the problem statement, there is an informative image in the html version of the problem statement, please view it in the normal applet window.

When wrapping your gifts this holiday season, you realize that you are wasting too much money on wrapping paper. To help you reduce the cost, you want to write a program that minimizes the wrapping paper used.

Your program will focus on one gift, which is a 3-dimensional box. The gift has 3 lengths which comprise its dimensions. In order to wrap it, you need to have a piece of paper that is long enough to wrap around the entire box in one direction, and that has enough hanging over the edges to cover the sides of the box. Therefore, there will be three seams, two on the sides and one on the top. In each seam, you want the overlap to be at least 1 inch (that is, at least one inch of paper is covered by another part of the paper).

The following image illustrates how the wrapping paper is used to wrap the box. The dotted lines are where edges of paper or the box are obscured by the paper. Pay close attention to where the seams are:

Create a class Giftwrap that contains the method minSize, which takes 2 arguments:
dimensions: a int[] which contains the three dimensions of the box, measured in inches.
paper: a int[] which contains the two dimensions of the paper you have to wrap the box with, measured in inches.

The method should return a int[] which contains the two dimensions of the paper you can cut from the given piece that will satisfactorily wrap the box and has the smallest area. If the two dimensions are not the same, the larger dimension should be first in the resulting int[]. If two different cuts produce the same area, return the one with the smallest first dimension. If no cut can satisfy the requirements, return {-1, -1}

Definition

Class:
Giftwrap
Method:
minSize
Parameters:
int[], int[]
Returns:
int[]
Method signature:
int[] minSize(int[] dimensions, int[] paper)
(be sure your method is public)

Notes

  • The box does not need to be wrapped in a specific orientation, but the paper must be aligned with the edges of the box. i.e. you cannot wrap the box diagonally.
  • The cut of paper must have edges parallel with the original paper.
  • You must use only one piece of paper to wrap the box, i.e. you cannot tape multiple pieces together.
  • If you can cover the box in a certain wrapping configuration, but there is not a 1 inch overlap at all seams, then you cannot use this configuration to wrap the box.

Constraints

  • dimensions will have exactly 3 elements.
  • Each element of dimensions will be between 5 and 50, inclusive.
  • paper will have exactly 2 elements.
  • Each element of paper will be between 5 and 250, inclusive.

Examples

  1. {5,6,7}

    {25,25}

    Returns: { 23, 13 }

    There are three ways to wrap this gift, which require 23x13, 25x12, or 27x12 inch paper sheets. The optimal way is with 23x13, and this is accomplished by positioning the box such that the faces that the paper covers last are 5x6. In reference to the diagram above, you can see one of these faces partially in steps 3 and 4.

  2. {5,7,6}

    {25,12}

    Returns: { 25, 12 }

    Same example, except now the 23x13 cannot be accomplished because it cannot be cut from the paper given (even though the paper has more total area than 23x13).

  3. {7,5,6}

    {22,22}

    Returns: { -1, -1 }

    Even though the paper is 185 square inches larger than the optimal wrapping size, the gift cannot be wrapped because neither dimension will satisfy the minimal length of 23.

  4. {5,5,15}

    {21,21}

    Returns: { 21, 21 }

    Two possible sizes exist, 21x21 and 41x11.

  5. {5,5,15}

    {10,50}

    Returns: { -1, -1 }

    Again, even though the area of the paper will more than cover the area of the box with 1 inch seams in any orientation, the box cannot be wrapped because 10 inches is too short for any orientation.

  6. {50,50,50}

    {201,101}

    Returns: { 201, 101 }

  7. {50,50,50}

    {201,100}

    Returns: { -1, -1 }

  8. {50,50,50}

    {200,101}

    Returns: { -1, -1 }

  9. {5,50,5}

    {11,56}

    Returns: { -1, -1 }

  10. {5,50,5}

    {111,11}

    Returns: { 111, 11 }

  11. {5,50,5}

    {11,111}

    Returns: { 111, 11 }

  12. {5,50,5}

    {111,111}

    Returns: { 56, 21 }

  13. {5,50,5}

    {11,11}

    Returns: { -1, -1 }

  14. {32,11,45}

    {250,250}

    Returns: { 87, 57 }

  15. {11,32,45}

    {44,155}

    Returns: { 113, 44 }

  16. {45,32,11}

    {57,155}

    Returns: { 87, 57 }

  17. {45,11,32}

    {81,92}

    Returns: { 87, 57 }

  18. {5,5,5}

    {5,5}

    Returns: { -1, -1 }

  19. {5,5,5}

    {20,20}

    Returns: { -1, -1 }

  20. {5,5,5}

    {50,12}

    Returns: { 21, 11 }

  21. {50,5,49}

    {100,100}

    Returns: { -1, -1 }

  22. {5,6,17}

    {50,50}

    Returns: { 23, 23 }

  23. {15, 17, 13}

    {147, 188}

    Returns: { 57, 31 }

  24. {19, 5, 11}

    {63, 96}

    Returns: { 33, 25 }

  25. {38, 42, 49}

    {88, 129}

    Returns: { -1, -1 }

  26. {42, 15, 21}

    {41, 13}

    Returns: { -1, -1 }

  27. {38, 46, 29}

    {127, 210}

    Returns: { 135, 76 }

  28. {24, 47, 35}

    {151, 144}

    Returns: { 119, 72 }

  29. {39, 49, 48}

    {86, 131}

    Returns: { -1, -1 }

  30. {31, 20, 29}

    {83, 244}

    Returns: { 99, 52 }

  31. {12, 12, 22}

    {107, 180}

    Returns: { 49, 35 }

  32. {44, 45, 24}

    {107, 61}

    Returns: { -1, -1 }

  33. {15, 29, 14}

    {128, 53}

    Returns: { 59, 44 }

  34. {29, 12, 27}

    {13, 215}

    Returns: { -1, -1 }

  35. {40, 47, 26}

    {143, 170}

    Returns: { 133, 74 }

  36. {50, 50, 12}

    {211, 121}

    Returns: { 125, 63 }

  37. {29, 7, 37}

    {199, 213}

    Returns: { 73, 45 }

  38. {20, 39, 21}

    {39, 161}

    Returns: { -1, -1 }

  39. {30, 18, 8}

    {69, 177}

    Returns: { 53, 39 }

  40. {22, 47, 13}

    {124, 123}

    Returns: { 71, 61 }

  41. {21, 41, 49}

    {168, 90}

    Returns: { 125, 71 }

  42. {13, 47, 23}

    {212, 42}

    Returns: { 121, 37 }

  43. {23, 13, 46}

    {167, 202}

    Returns: { 73, 60 }

  44. {48, 15, 7}

    {250, 47}

    Returns: { 56, 45 }

  45. {42, 19, 11}

    {77, 179}

    Returns: { 61, 54 }

  46. {22, 21, 11}

    {99, 188}

    Returns: { 65, 34 }

  47. {33, 39, 23}

    {212, 36}

    Returns: { -1, -1 }

  48. {25, 28, 25}

    {25, 132}

    Returns: { -1, -1 }

  49. {44, 37, 44}

    {87, 175}

    Returns: { 163, 82 }

  50. {45, 24, 29}

    {52, 163}

    Returns: { -1, -1 }

  51. { 15, 5, 5 }

    { 25, 25 }

    Returns: { 21, 21 }

  52. { 5, 7, 6 }

    { 12, 25 }

    Returns: { 25, 12 }

  53. { 21, 44, 32 }

    { 250, 250 }

    Returns: { 107, 66 }

  54. { 5, 5, 5 }

    { 25, 25 }

    Returns: { 21, 11 }

  55. { 5, 6, 7 }

    { 25, 25 }

    Returns: { 23, 13 }

  56. { 5, 5, 15 }

    { 10, 50 }

    Returns: { -1, -1 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: