Statistics

Problem Statement for "LameKnight"

Problem Statement

A lame knight is located at the bottom-left corner of a height x width chessboard. Unlike a healthy knight, a lame knight can only make moves where he goes to the right. The only possible moves are:

  1. 2 cells up, 1 cell right;
  2. 1 cell up, 2 cells right;
  3. 1 cell down, 2 cells right;
  4. 2 cells down, 1 cell right.
The knight will make one trip, and he wants to maximize the number of visited cells. The knight's starting cell counts toward this number. There is also one restriction for the knight's trip: it must contain each kind of a move at least once, unless it is shorter than 4 moves. If the knight makes less than 4 moves (thus visiting less than 5 cells), his moves are not limited in any way. Return the maximal number of cells the knight can visit during one trip, including the initial cell.

Definition

Class:
LameKnight
Method:
maxCells
Parameters:
int, int
Returns:
int
Method signature:
int maxCells(int height, int width)
(be sure your method is public)

Constraints

  • height will be between 1 and 2,000,000,000, inclusive.
  • width will be between 1 and 2,000,000,000, inclusive.

Examples

  1. 100

    50

    Returns: 48

    1 move of kind 2, 1 move of kind 3, 23 moves of kind 1 and 22 moves of kind 4.

  2. 1

    1

    Returns: 1

    There are no possible moves here, so the only visited cell is the starting cell.

  3. 17

    5

    Returns: 4

    It's possible to visit 5 cells (making 4 moves of kind 1 for example), but it's impossible to make it by 4 different moves. So, the best strategy here is to make 3 moves (thus visiting 4 cells).

  4. 3

    2000000000

    Returns: 1999999998

  5. 2000000000

    2000000000

    Returns: 1999999998

  6. 2

    1999999999

    Returns: 4

  7. 2

    2000000000

    Returns: 4

  8. 1

    2000000000

    Returns: 1

  9. 2

    1

    Returns: 1

  10. 2

    2

    Returns: 1

  11. 2

    3

    Returns: 2

  12. 2

    4

    Returns: 2

  13. 2

    5

    Returns: 3

  14. 2

    6

    Returns: 3

  15. 2

    7

    Returns: 4

  16. 2

    8

    Returns: 4

  17. 2

    9

    Returns: 4

  18. 2

    10

    Returns: 4

  19. 3

    1

    Returns: 1

  20. 3

    2

    Returns: 2

  21. 3

    3

    Returns: 3

  22. 3

    4

    Returns: 4

  23. 3

    5

    Returns: 4

  24. 3

    6

    Returns: 4

  25. 3

    7

    Returns: 5

  26. 3

    8

    Returns: 6

  27. 3

    9

    Returns: 7

  28. 3

    10

    Returns: 8

  29. 4

    10

    Returns: 8

  30. 3

    199923

    Returns: 199921

  31. 2

    12493

    Returns: 4

  32. 2

    1999969992

    Returns: 4

  33. 3

    1997999991

    Returns: 1997999989

  34. 20

    4

    Returns: 4

    4 cells can be visited using 2 moves of kind 1 and 1 move of kind 4.

  35. 2

    100

    Returns: 4

  36. 200000000

    200000000

    Returns: 199999998

  37. 2

    10000000

    Returns: 4

  38. 2

    200

    Returns: 4

  39. 2

    1000

    Returns: 4

  40. 2

    11111110

    Returns: 4

  41. 1

    10

    Returns: 1

  42. 2

    11

    Returns: 4

  43. 5

    1000

    Returns: 998

  44. 2

    2222

    Returns: 4

  45. 200

    200

    Returns: 198

  46. 6

    2

    Returns: 2

  47. 7

    2

    Returns: 2

  48. 5

    2

    Returns: 2

  49. 1

    100

    Returns: 1

  50. 1

    5

    Returns: 1

  51. 1

    8

    Returns: 1

  52. 1

    80

    Returns: 1

  53. 20

    6

    Returns: 4

  54. 2

    100000

    Returns: 4

  55. 3

    50

    Returns: 48

  56. 1

    11

    Returns: 1

  57. 2

    50

    Returns: 4

  58. 100

    6

    Returns: 4

  59. 100

    2

    Returns: 2

  60. 1

    2222

    Returns: 1

  61. 1000

    2

    Returns: 2

  62. 8

    6

    Returns: 4

  63. 2

    10000

    Returns: 4

  64. 2

    17

    Returns: 4

  65. 1

    100000

    Returns: 1

  66. 2

    500000

    Returns: 4

  67. 1999999999

    2

    Returns: 2

  68. 10

    2

    Returns: 2

  69. 1

    200

    Returns: 1

  70. 2

    20

    Returns: 4

  71. 1

    10000

    Returns: 1

  72. 1

    1000

    Returns: 1

  73. 7

    6

    Returns: 4

  74. 3

    1000

    Returns: 998

  75. 2000000000

    1999999999

    Returns: 1999999997

  76. 2

    30

    Returns: 4

  77. 234234

    123135

    Returns: 123133

  78. 2

    6666666

    Returns: 4

  79. 6

    1

    Returns: 1

  80. 1

    10000000

    Returns: 1

  81. 500000234

    637836587

    Returns: 637836585

  82. 10

    1

    Returns: 1

  83. 100

    1

    Returns: 1

  84. 20000000

    20000000

    Returns: 19999998

  85. 1

    20000

    Returns: 1

  86. 3

    100

    Returns: 98

  87. 1

    1000000

    Returns: 1

  88. 2

    15

    Returns: 4

  89. 2

    19999

    Returns: 4

  90. 200

    2

    Returns: 2

  91. 1

    49

    Returns: 1

  92. 1

    7

    Returns: 1

  93. 3

    100000

    Returns: 99998

  94. 60

    4

    Returns: 4

  95. 1

    2

    Returns: 1

  96. 1000000000

    1000000000

    Returns: 999999998

  97. 2

    1000000

    Returns: 4

  98. 1

    50

    Returns: 1

  99. 6

    30

    Returns: 28

  100. 10

    100

    Returns: 98

  101. 4

    3

    Returns: 3

  102. 1000

    7

    Returns: 5

  103. 3

    321

    Returns: 319

  104. 1

    6

    Returns: 1

  105. 100

    2000000000

    Returns: 1999999998

  106. 3

    2000000

    Returns: 1999998

  107. 2000000

    1

    Returns: 1

  108. 100

    3

    Returns: 3

  109. 100

    7

    Returns: 5

  110. 120

    90

    Returns: 88

  111. 3

    60

    Returns: 58

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: