Statistics

Problem Statement for "FoldingPaper2"

Problem Statement

You have a rectangular piece of paper. Its dimensions are W times H. You want to have a paper with area A instead. Therefore, you decided to fold the paper you have. In each step you can fold the paper according to a straight line. There are two restrictions: First, that line must always be parallel to one of the rectangle's sides. Second, after each fold both dimensions of the new rectangle must be integers again.

For example, suppose that your paper is 5 units wide and 3 units tall. If you fold it according to a vertical line that is 4 units to the right of its left side, you will obtain a rectangle that is 4 units wide and 3 units tall. If you fold it according to a horizontal line that is 1 unit below the top of the rectangle, you will get a rectangle that is 5 units wide and 2 units tall.

You are given the ints W, H, and A. If it is impossible to fold the paper into a valid rectangle with area A, return -1. Otherwise, return the smallest number of times you need to fold the paper.

Definition

Class:
FoldingPaper2
Method:
solve
Parameters:
int, int, int
Returns:
int
Method signature:
int solve(int W, int H, int A)
(be sure your method is public)

Constraints

  • H, W will be between 1 and 1,000,000,000, inclusive.
  • A will be between 1 and 100,000, inclusive.

Examples

  1. 5

    3

    12

    Returns: 1

    The solution in this case is the first example mentioned above.

  2. 2

    2

    3

    Returns: -1

    A 2x2 square cannot be folded into a rectangle with area 3. Note that a rectangle that is 1.5 units wide and 2 units tall is not a solution: both dimensions of all rectangles you produce must be integers.

  3. 4

    4

    1

    Returns: 4

  4. 127

    129

    72

    Returns: 8

  5. 1

    100000

    100000

    Returns: 0

    The paper already has the desired area, so no folding is necessary.

  6. 1

    1

    2

    Returns: -1

  7. 1000000000

    1000000000

    100000

    Returns: 44

  8. 1000000000

    1000000000

    1

    Returns: 60

  9. 10000

    10000

    9999

    Returns: 14

  10. 101

    103

    10403

    Returns: 0

  11. 103

    101

    10403

    Returns: 0

  12. 105

    100

    10403

    Returns: -1

  13. 103

    201

    10403

    Returns: 1

  14. 207

    202

    10403

    Returns: 3

  15. 207

    206

    10403

    Returns: 3

  16. 206

    207

    10403

    Returns: 3

  17. 6465

    103

    10403

    Returns: 7

  18. 9999

    9999

    10000

    Returns: 14

  19. 84

    286

    3003

    Returns: 3

  20. 8

    8

    35

    Returns: 2

  21. 7

    7

    35

    Returns: 1

  22. 6

    6

    35

    Returns: -1

  23. 16

    16

    128

    Returns: 1

  24. 8

    8

    128

    Returns: -1

  25. 1

    100000

    99999

    Returns: 1

  26. 3

    100000

    99999

    Returns: 2

  27. 100000

    3

    99999

    Returns: 2

  28. 4

    74

    222

    Returns: 1

  29. 4

    75

    222

    Returns: 2

  30. 4

    149

    222

    Returns: 2

  31. 4

    110

    222

    Returns: 2

  32. 4

    111

    222

    Returns: 1

  33. 3

    148

    222

    Returns: 1

  34. 3

    147

    222

    Returns: 1

  35. 3

    149

    222

    Returns: 2

  36. 234624

    35235

    108

    Returns: 27

  37. 657356

    54542

    108

    Returns: 29

  38. 30

    29

    225

    Returns: 2

  39. 730

    12

    729

    Returns: 4

  40. 100000

    20056

    208

    Returns: 24

  41. 75

    279

    225

    Returns: 7

  42. 775

    279

    225

    Returns: 10

  43. 1

    20

    5

    Returns: 2

  44. 1

    11

    5

    Returns: 2

  45. 1

    21

    5

    Returns: 3

  46. 9

    3

    12

    Returns: 2

  47. 1000000000

    1000000000

    12

    Returns: 57

  48. 1000000000

    3

    100000

    Returns: 16

  49. 1000000000

    1000000000

    3

    Returns: 59

  50. 99

    999

    23

    Returns: 13

  51. 10

    10

    6

    Returns: 5

  52. 15

    39

    133

    Returns: 4

  53. 1000000000

    1000000000

    99999

    Returns: 44

  54. 1247

    12

    13299

    Returns: 2

  55. 7

    7

    9

    Returns: 4

  56. 864682

    824

    100000

    Returns: 14

  57. 16

    5

    20

    Returns: 2

  58. 999999999

    999999999

    55566

    Returns: 45

  59. 245344672

    45632342

    56322

    Returns: 38

  60. 50

    20000

    5678

    Returns: 8

  61. 7

    7

    36

    Returns: 2

  62. 2

    10000000

    2

    Returns: 24

  63. 4

    4

    2

    Returns: 3

  64. 1

    1

    8

    Returns: -1

  65. 1000000000

    99935080

    4096

    Returns: 45

  66. 99

    195

    35

    Returns: 10

  67. 3

    16

    12

    Returns: 2

  68. 100000

    1

    100000

    Returns: 0

  69. 1000000

    1000000

    1

    Returns: 40

  70. 100000

    10000000

    1

    Returns: 41

  71. 3

    8

    16

    Returns: 1

  72. 3

    16

    6

    Returns: 3

  73. 1000000000

    747172737

    1

    Returns: 60

  74. 8

    8

    49

    Returns: 2

  75. 156

    95

    35

    Returns: 9

  76. 1232143

    99643

    23

    Returns: 33

  77. 536870912

    536870912

    2

    Returns: 57

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: