Statistics

Problem Statement for "HyperKnight"

Problem Statement

Fernando loves to play chess. One day he decided to play chess on an unusually large rectangular board. To compensate for the board's size he also decided to change the distance a knight can move in a single jump.

To describe the moves easily, we will now introduce a coordinate system. Each cell of the chessboard can be described using two integers (r,c): its row number and its column number. Now, if we have a piece at (r,c), the move (x,y) takes the piece to the cell (r+x,c+y).

The new chess piece will be called an (a,b)-hyperknight. The hyperknight always has 8 possible moves: (+a,+b), (+a,-b), (-a,+b), (-a,-b), (+b,+a), (+b,-a), (-b,+a), and (-b,-a). Note that the original chess knight is a (2,1)-hyperknight.

Of course, as the chessboard is finite, it is not always possible to make each of the 8 moves. Some of them may cause our hyperknight to leave the chessboard. A move is called valid if the destination cell is on the chessboard. Fernando would like to know the number of cells on his board such that his hyperknight will have exactly k valid moves from that cell.

You are given the ints a, b, numRows, numColumns and k. The values numRows and numColumns define the number of rows and number of columns on the chessboard, respectively. The other three values were already explained above. Compute and return the number of cells on the chessboard that have exactly k valid (a,b)-hyperknight moves.

Definition

Class:
HyperKnight
Method:
countCells
Parameters:
int, int, int, int, int
Returns:
long
Method signature:
long countCells(int a, int b, int numRows, int numColumns, int k)
(be sure your method is public)

Notes

  • If you wish, you may assume that the rows are numbered 0 through numRows-1 and columns 0 through numColumns-1. However, note that the actual row/column numbers do not matter, as long as they are consecutive.

Constraints

  • a will be between 1 and 1,000,000,000 (10^9), inclusive.
  • b will be between 1 and 1,000,000,000 (10^9), inclusive.
  • a will not be equal to b.
  • numRows will be between 1 and 1,000,000,000 (10^9), inclusive.
  • numColumns will be between 1 and 1,000,000,000 (10^9), inclusive.
  • 2*max(a,b) will be strictly less than min(numRows,numColumns).
  • k will be between 0 and 8, inclusive.

Examples

  1. 2

    1

    8

    8

    4

    Returns: 20

    This is a standard chessboard. We have a traditional chess knight and we are looking for cells such that the knight has exactly 4 valid moves.

  2. 3

    2

    8

    8

    2

    Returns: 16

  3. 1

    3

    7

    11

    0

    Returns: 0

  4. 3

    2

    10

    20

    8

    Returns: 56

  5. 1

    4

    100

    10

    6

    Returns: 564

  6. 2

    3

    1000000000

    1000000000

    8

    Returns: 999999988000000036

  7. 2

    3

    7

    7

    1

    Returns: 0

  8. 2

    3

    7

    7

    2

    Returns: 16

  9. 2

    3

    7

    7

    3

    Returns: 16

  10. 2

    3

    7

    7

    4

    Returns: 12

  11. 2

    3

    7

    7

    5

    Returns: 0

  12. 2

    3

    7

    7

    6

    Returns: 4

  13. 2

    3

    7

    7

    7

    Returns: 0

  14. 2

    3

    7

    7

    8

    Returns: 1

  15. 499999998

    499999999

    1000000000

    1000000000

    0

    Returns: 0

  16. 499999998

    499999999

    1000000000

    1000000000

    1

    Returns: 0

  17. 499999998

    499999999

    1000000000

    1000000000

    2

    Returns: 999999992000000016

  18. 499999998

    499999999

    1000000000

    1000000000

    3

    Returns: 3999999984

  19. 499999998

    499999999

    1000000000

    1000000000

    4

    Returns: 3999999988

  20. 499999998

    499999999

    1000000000

    1000000000

    5

    Returns: 0

  21. 499999998

    499999999

    1000000000

    1000000000

    6

    Returns: 8

  22. 499999998

    499999999

    1000000000

    1000000000

    7

    Returns: 0

  23. 499999998

    499999999

    1000000000

    1000000000

    8

    Returns: 4

  24. 2

    1

    20001

    1000000000

    0

    Returns: 0

  25. 2

    1

    20001

    1000000000

    1

    Returns: 0

  26. 2

    1

    20001

    1000000000

    2

    Returns: 4

  27. 2

    1

    20001

    1000000000

    3

    Returns: 8

  28. 2

    1

    20001

    1000000000

    4

    Returns: 2000039990

  29. 2

    1

    20001

    1000000000

    5

    Returns: 0

  30. 2

    1

    20001

    1000000000

    6

    Returns: 2000039986

  31. 2

    1

    20001

    1000000000

    7

    Returns: 0

  32. 2

    1

    20001

    1000000000

    8

    Returns: 19996999920012

  33. 10000

    5000

    20001

    1000000000

    0

    Returns: 0

  34. 10000

    5000

    20001

    1000000000

    1

    Returns: 0

  35. 10000

    5000

    20001

    1000000000

    2

    Returns: 100000000

  36. 10000

    5000

    20001

    1000000000

    3

    Returns: 200000000

  37. 10000

    5000

    20001

    1000000000

    4

    Returns: 9999900010000

  38. 10000

    5000

    20001

    1000000000

    5

    Returns: 0

  39. 10000

    5000

    20001

    1000000000

    6

    Returns: 9999800010000

  40. 10000

    5000

    20001

    1000000000

    7

    Returns: 0

  41. 10000

    5000

    20001

    1000000000

    8

    Returns: 999980000

  42. 1

    2

    1000000000

    1000000000

    0

    Returns: 0

  43. 1

    2

    1000000000

    1000000000

    1

    Returns: 0

  44. 1

    2

    1000000000

    1000000000

    2

    Returns: 4

  45. 1

    2

    1000000000

    1000000000

    3

    Returns: 8

  46. 1

    2

    1000000000

    1000000000

    4

    Returns: 3999999988

  47. 1

    2

    1000000000

    1000000000

    5

    Returns: 0

  48. 1

    2

    1000000000

    1000000000

    6

    Returns: 3999999984

  49. 1

    2

    1000000000

    1000000000

    7

    Returns: 0

  50. 1

    2

    1000000000

    1000000000

    8

    Returns: 999999992000000016

  51. 1

    2

    1000000000

    5

    0

    Returns: 0

  52. 1

    2

    1000000000

    5

    1

    Returns: 0

  53. 1

    2

    1000000000

    5

    2

    Returns: 4

  54. 1

    2

    1000000000

    5

    3

    Returns: 8

  55. 1

    2

    1000000000

    5

    4

    Returns: 1999999998

  56. 1

    2

    1000000000

    5

    5

    Returns: 0

  57. 1

    2

    1000000000

    5

    6

    Returns: 1999999994

  58. 1

    2

    1000000000

    5

    7

    Returns: 0

  59. 1

    2

    1000000000

    5

    8

    Returns: 999999996

  60. 499999999

    1

    1000000000

    1000000000

    0

    Returns: 0

  61. 499999999

    1

    1000000000

    1000000000

    1

    Returns: 0

  62. 499999999

    1

    1000000000

    1000000000

    2

    Returns: 4

  63. 499999999

    1

    1000000000

    1000000000

    3

    Returns: 3999999984

  64. 499999999

    1

    1000000000

    1000000000

    4

    Returns: 999999992000000024

  65. 499999999

    1

    1000000000

    1000000000

    5

    Returns: 0

  66. 499999999

    1

    1000000000

    1000000000

    6

    Returns: 3999999984

  67. 499999999

    1

    1000000000

    1000000000

    7

    Returns: 0

  68. 499999999

    1

    1000000000

    1000000000

    8

    Returns: 4

  69. 19205425

    29027233

    79816846

    73398506

    2

    Returns: 1475393397722500

  70. 19205425

    29027233

    79816846

    73398506

    3

    Returns: 1509055975267200

  71. 19205425

    29027233

    79816846

    73398506

    4

    Returns: 1811160782212456

  72. 19205425

    29027233

    79816846

    73398506

    6

    Returns: 728904265614720

  73. 19205425

    29027233

    79816846

    73398506

    8

    Returns: 333922829215200

  74. 36411905

    49189985

    123331332

    139724323

    2

    Returns: 5303307302916100

  75. 36411905

    49189985

    123331332

    139724323

    3

    Returns: 3722193880339200

  76. 36411905

    49189985

    123331332

    139724323

    4

    Returns: 5481023866919750

  77. 36411905

    49189985

    123331332

    139724323

    6

    Returns: 1694263899854400

  78. 36411905

    49189985

    123331332

    139724323

    8

    Returns: 1031597918358786

  79. 37909854

    42557194

    128417691

    92857213

    2

    Returns: 5748628121205264

  80. 37909854

    42557194

    128417691

    92857213

    3

    Returns: 1409439847106880

  81. 37909854

    42557194

    128417691

    92857213

    4

    Returns: 3956693595793024

  82. 5347410

    33895789

    74759886

    97588821

    8

    Returns: 207636366774844

  83. 42207223

    39173184

    115662001

    97975491

    4

    Returns: 3547412635778884

  84. 42207223

    39173184

    115662001

    97975491

    6

    Returns: 271902079870800

  85. 42207223

    39173184

    115662001

    97975491

    8

    Returns: 423749499494975

  86. 6654070

    1356936

    57822120

    24685929

    2

    Returns: 7365101232384

  87. 6654070

    1356936

    57822120

    24685929

    3

    Returns: 57502974571392

  88. 26174793

    2712259

    85355565

    96339217

    3

    Returns: 509091752034448

  89. 26174793

    2712259

    85355565

    96339217

    4

    Returns: 2619626079170604

  90. 26174793

    2712259

    85355565

    96339217

    6

    Returns: 3613024234951480

  91. 26174793

    2712259

    85355565

    96339217

    8

    Returns: 1451920837003749

  92. 38549418

    49711042

    144624062

    105034741

    2

    Returns: 5944230512554896

  93. 38549418

    49711042

    144624062

    105034741

    8

    Returns: 253703198235546

  94. 39483358

    9722546

    123397642

    96761518

    2

    Returns: 378111602888464

  95. 39483358

    9722546

    123397642

    96761518

    6

    Returns: 3703776385142272

  96. 39483358

    9722546

    123397642

    96761518

    8

    Returns: 790639530846652

  97. 35834099

    7025192

    73801792

    89315676

    2

    Returns: 197413290547456

  98. 35834099

    7025192

    73801792

    89315676

    8

    Returns: 37652553175932

  99. 4781822

    9360408

    54482604

    24850751

    2

    Returns: 91463286558736

  100. 4781822

    9360408

    54482604

    24850751

    3

    Returns: 175151866109536

  101. 4781822

    9360408

    54482604

    24850751

    4

    Returns: 484491324356196

  102. 43521866

    5243715

    101731108

    129509489

    3

    Returns: 1605757716567720

  103. 43521866

    5243715

    101731108

    129509489

    4

    Returns: 6460256857533394

  104. 43521866

    5243715

    101731108

    129509489

    6

    Returns: 4375432510194166

  105. 43521866

    5243715

    101731108

    129509489

    8

    Returns: 623710540183632

  106. 11098020

    36554824

    107799910

    74593434

    2

    Returns: 492664191681600

  107. 11098020

    36554824

    107799910

    74593434

    3

    Returns: 2260160959424640

  108. 11098020

    36554824

    107799910

    74593434

    4

    Returns: 3395116095947584

  109. 11098020

    36554824

    107799910

    74593434

    6

    Returns: 1841751299645184

  110. 18607318

    20353033

    58228002

    54010191

    3

    Returns: 259864593138960

  111. 18607318

    20353033

    58228002

    54010191

    4

    Returns: 1159370722873696

  112. 18607318

    20353033

    58228002

    54010191

    6

    Returns: 107627034157230

  113. 18607318

    20353033

    58228002

    54010191

    8

    Returns: 233114026786000

  114. 43265408

    3290218

    90125504

    103363137

    4

    Returns: 6526481887540324

  115. 43265408

    3290218

    90125504

    103363137

    6

    Returns: 1633147131813420

  116. 43265408

    3290218

    90125504

    103363137

    8

    Returns: 60506942310848

  117. 22620589

    11861535

    67151929

    50577031

    2

    Returns: 562784050224900

  118. 22620589

    11861535

    67151929

    50577031

    3

    Returns: 1020951164703120

  119. 22620589

    11861535

    67151929

    50577031

    4

    Returns: 1109402065853944

  120. 22620589

    11861535

    67151929

    50577031

    6

    Returns: 586295367505232

  121. 22620589

    11861535

    67151929

    50577031

    8

    Returns: 116912546455603

  122. 1

    2

    5

    5

    0

    Returns: 0

  123. 1

    2

    5

    5

    1

    Returns: 0

  124. 1

    2

    5

    5

    2

    Returns: 4

  125. 1

    2

    5

    5

    3

    Returns: 8

  126. 1

    2

    5

    5

    4

    Returns: 8

  127. 1

    2

    5

    5

    5

    Returns: 0

  128. 1

    2

    5

    5

    6

    Returns: 4

  129. 1

    2

    5

    5

    7

    Returns: 0

  130. 1

    2

    5

    5

    8

    Returns: 1

  131. 3000013

    5000017

    987654321

    123456789

    3

    Returns: 48000304000416

  132. 4

    2

    100

    500

    3

    Returns: 32

  133. 1

    2

    8

    8

    3

    Returns: 8

  134. 2

    1

    8

    8

    3

    Returns: 8

  135. 3

    1

    8

    8

    3

    Returns: 16

  136. 156

    178

    100000000

    100000000

    4

    Returns: 62399779792

  137. 2

    3

    1000000000

    1000000000

    3

    Returns: 16

  138. 2

    1

    1000000000

    1000000000

    8

    Returns: 999999992000000016

  139. 111111

    1111111

    1000000000

    1000000000

    3

    Returns: 888888000000

  140. 2

    1

    100

    100

    3

    Returns: 8

  141. 2

    3

    1000000000

    1000000000

    4

    Returns: 7999999956

  142. 2

    1

    5

    5

    3

    Returns: 8

  143. 5

    99

    1000

    1000

    3

    Returns: 3760

  144. 4

    2

    1000

    1000

    3

    Returns: 32

  145. 3

    2

    8

    8

    3

    Returns: 16

  146. 10

    8

    100

    100

    4

    Returns: 2576

  147. 50

    40

    200

    200

    3

    Returns: 3200

  148. 1

    2

    1000

    1000

    8

    Returns: 992016

  149. 10

    7

    10000

    10000

    3

    Returns: 168

  150. 19

    57

    200

    312

    3

    Returns: 5776

  151. 600000

    500000

    1000000000

    1000000000

    3

    Returns: 400000000000

  152. 2

    1

    100000

    100000

    3

    Returns: 8

  153. 499999999

    499999998

    1000000000

    1000000000

    3

    Returns: 3999999984

  154. 5

    3

    10000

    10000

    3

    Returns: 48

  155. 3

    1

    7

    7

    5

    Returns: 0

  156. 11

    234

    10000

    20000

    3

    Returns: 19624

  157. 1000

    1200

    100000

    120000

    3

    Returns: 1600000

  158. 2

    3

    8

    8

    3

    Returns: 16

  159. 3

    5

    100

    100

    4

    Returns: 1096

  160. 5

    70

    1000000000

    1000000000

    6

    Returns: 259999963600

  161. 10

    30

    100

    1000

    3

    Returns: 1600

  162. 499999998

    499999990

    1000000000

    1000000000

    2

    Returns: 999999960000000400

  163. 2

    1

    1000000000

    1000000000

    4

    Returns: 3999999988

  164. 26

    16

    567

    123

    5

    Returns: 0

  165. 1

    2

    10

    10

    3

    Returns: 8

  166. 2

    1

    10

    10

    3

    Returns: 8

  167. 99999999

    999999

    1000000000

    1000000000

    4

    Returns: 42403996807999992

  168. 23

    4

    2542

    5463

    3

    Returns: 608

  169. 1

    3

    7

    7

    3

    Returns: 16

  170. 99

    100

    100000

    100000

    2

    Returns: 39204

  171. 400000000

    200000000

    1000000000

    1000000000

    3

    Returns: 320000000000000000

  172. 1

    3

    1000000000

    1000000000

    4

    Returns: 3999999992

  173. 4

    3

    14

    15

    3

    Returns: 24

  174. 10

    20

    100

    100

    3

    Returns: 800

  175. 49999999

    50000000

    100000003

    100000007

    4

    Returns: 999999984

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: