Statistics

Problem Statement for "KnightCircuit2"

Problem Statement

The knight is a chess piece that moves by jumping: two cells in one direction, one in the other. Formally, a knight standing on the cell (x,y) can move to any of the following eight cells: (x+2,y+1), (x+2,y-1), (x-2,y+1), (x-2,y-1), (x+1,y+2), (x+1,y-2), (x-1,y+2), and (x-1,y-2). Of course, if the knight is close to the edge of the board, some of these cells might not be on the board. It is not allowed to jump to a cell that is not on the board.

A knight circuit is a sequence of cells on a chessboard that starts and ends with the same cell. Each consecutive pair of cells in the knight circuit must correspond to a single jump of the knight. The knight circuit may visit each cell arbitrarily many times. The size of a knight circuit is the number of different cells visited by the circuit.

You are given the ints w and h: the width (in columns) and the height (in rows) of a rectangular chessboard. Return the maximum knight circuit size that can be obtained on the given board. You are free to choose any cell as the start of your circuit.

Definition

Class:
KnightCircuit2
Method:
maxSize
Parameters:
int, int
Returns:
int
Method signature:
int maxSize(int w, int h)
(be sure your method is public)

Constraints

  • w and h will each be between 1 and 45000, inclusive.

Examples

  1. 1

    1

    Returns: 1

    Note that a sequence that consists of a single cell is considered to be a valid knight circuit.

  2. 15

    2

    Returns: 8

    If you start at any corner of the board, it is possible to move the knight to visit 8 cells, and then do the same moves in reverse in order to return to the starting cell. One possibility for the first eight cells of an optimal knight circuit is shown below: 1...3...5...7.. ..2...4...6...8

  3. 100

    100

    Returns: 10000

    It is possible to make a Knight circuit that contains all the cells on the board.

  4. 3

    3

    Returns: 8

  5. 5

    4

    Returns: 20

  6. 3

    2

    Returns: 2

  7. 1

    45000

    Returns: 1

  8. 45000

    1

    Returns: 1

  9. 1

    22279

    Returns: 1

  10. 1

    39878

    Returns: 1

  11. 43270

    1

    Returns: 1

  12. 13784

    1

    Returns: 1

  13. 1

    27255

    Returns: 1

  14. 29043

    1

    Returns: 1

  15. 1

    5043

    Returns: 1

  16. 1

    21932

    Returns: 1

  17. 13510

    1

    Returns: 1

  18. 39576

    1

    Returns: 1

  19. 2

    2

    Returns: 1

  20. 2

    15463

    Returns: 7732

  21. 23900

    2

    Returns: 11950

  22. 10827

    2

    Returns: 5414

  23. 27471

    2

    Returns: 13736

  24. 10856

    2

    Returns: 5428

  25. 22189

    2

    Returns: 11095

  26. 2

    16267

    Returns: 8134

  27. 11416

    2

    Returns: 5708

  28. 2

    7641

    Returns: 3821

  29. 2

    5887

    Returns: 2944

  30. 9663

    2

    Returns: 4832

  31. 2

    7417

    Returns: 3709

  32. 2

    44820

    Returns: 22410

  33. 12338

    2

    Returns: 6169

  34. 11540

    2

    Returns: 5770

  35. 2

    33896

    Returns: 16948

  36. 39060

    2

    Returns: 19530

  37. 34885

    2

    Returns: 17443

  38. 39519

    2

    Returns: 19760

  39. 7236

    2

    Returns: 3618

  40. 3

    29038

    Returns: 87114

  41. 3

    39515

    Returns: 118545

  42. 11345

    3

    Returns: 34035

  43. 2473

    3

    Returns: 7419

  44. 26591

    3

    Returns: 79773

  45. 3

    25053

    Returns: 75159

  46. 10661

    3

    Returns: 31983

  47. 3

    362

    Returns: 1086

  48. 3

    32740

    Returns: 98220

  49. 3

    5936

    Returns: 17808

  50. 3

    8468

    Returns: 25404

  51. 3

    12128

    Returns: 36384

  52. 3

    31858

    Returns: 95574

  53. 3

    34476

    Returns: 103428

  54. 28802

    3

    Returns: 86406

  55. 32913

    3

    Returns: 98739

  56. 18628

    3

    Returns: 55884

  57. 3

    8306

    Returns: 24918

  58. 19097

    3

    Returns: 57291

  59. 25406

    3

    Returns: 76218

  60. 2541

    20856

    Returns: 52995096

  61. 14419

    12565

    Returns: 181174735

  62. 38541

    42422

    Returns: 1634986302

  63. 11035

    14984

    Returns: 165348440

  64. 14034

    5341

    Returns: 74955594

  65. 9038

    19759

    Returns: 178581842

  66. 8390

    11828

    Returns: 99236920

  67. 9918

    28487

    Returns: 282534066

  68. 30892

    30300

    Returns: 936027600

  69. 18127

    12992

    Returns: 235505984

  70. 34788

    34923

    Returns: 1214901324

  71. 20739

    15623

    Returns: 324005397

  72. 23954

    26913

    Returns: 644674002

  73. 13419

    28274

    Returns: 379408806

  74. 28689

    4500

    Returns: 129100500

  75. 28530

    31815

    Returns: 907681950

  76. 22985

    1063

    Returns: 24433055

  77. 17051

    34304

    Returns: 584917504

  78. 13245

    30758

    Returns: 407389710

  79. 950

    19702

    Returns: 18716900

  80. 31665

    29950

    Returns: 948366750

  81. 41419

    14625

    Returns: 605752875

  82. 38383

    37867

    Returns: 1453449061

  83. 12259

    348

    Returns: 4266132

  84. 40450

    22196

    Returns: 897828200

  85. 2614

    17017

    Returns: 44482438

  86. 25447

    27169

    Returns: 691369543

  87. 16903

    16123

    Returns: 272527069

  88. 31014

    17527

    Returns: 543582378

  89. 7177

    35843

    Returns: 257245211

  90. 5

    5

    Returns: 25

  91. 4

    4

    Returns: 16

  92. 1

    100

    Returns: 1

  93. 45000

    45000

    Returns: 2025000000

  94. 3

    5

    Returns: 15

  95. 51

    51

    Returns: 2601

  96. 4

    2

    Returns: 2

  97. 3

    4

    Returns: 12

  98. 2

    100

    Returns: 50

  99. 99

    98

    Returns: 9702

  100. 3

    7

    Returns: 21

  101. 2

    4

    Returns: 2

  102. 16

    2

    Returns: 8

  103. 1

    3

    Returns: 1

  104. 1

    7

    Returns: 1

  105. 1

    123

    Returns: 1

  106. 99

    45000

    Returns: 4455000

  107. 1

    10

    Returns: 1

  108. 33

    3

    Returns: 99

  109. 1

    1234

    Returns: 1

  110. 9

    45000

    Returns: 405000

  111. 5

    2

    Returns: 3

  112. 10

    45000

    Returns: 450000

  113. 45000

    50

    Returns: 2250000

  114. 2

    45000

    Returns: 22500

  115. 4

    45000

    Returns: 180000

  116. 10

    3

    Returns: 30

  117. 45000

    98

    Returns: 4410000

  118. 1

    199

    Returns: 1

  119. 80

    45000

    Returns: 3600000

  120. 45000

    99

    Returns: 4455000

  121. 3

    45000

    Returns: 135000

  122. 2

    3

    Returns: 2

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: