Statistics

Problem Statement for "RectangleBreaking"

Problem Statement

Rectangle breaking game is played with a collection of rectangles. Each rectangle is divided into a grid of unit squares. The rectangles have a fixed orientation, hence each rectangle has some number of rows and some number of columns.

A rectangle with R rows and C columns will be denoted RxC.


The game is played by two players, Hannah and Victor. Whenever it's Hannah's turn, she chooses a rectangle and breaks it horizontally. (The two new pieces have the same number of columns as the original. E.g., she can break a 4x7 rectangle into a 1x7 rectangle and a 3x7 rectangle.) Whenever it's Victor's turn, he chooses a rectangle and breaks it vertically.

Of course, a rectangle can only be broken along one of the grid lines, and a rectangle can only be chosen if it can actually be broken in the chosen direction. The current player gets to choose where exactly to break the rectangle they chose, if there are multiple ways to do so.

Whoever cannot make a valid move loses the game.


This is obviously a finite game with perfect information. This game is not impartial, as in any given position each player has a different set of valid moves they can make. Such games are called partisan games.

We will now assume that both players play the game optimally. Under this assumption, each position in a partisan game is of one of four possible types. In our game we will call these "first", "second", "Hannah", and "Victor". Their meaning is as follows:

  • "first": The player who makes the first move from this position wins the game. (I.e., if the players are in this position and it's Hannah's turn, she has a winning strategy. If they are in the same position but it's Victor's turn, he has a winning strategy.)
  • "second": The player who makes the second move from this position wins the game. (I.e., whoever must make the first move loses.)
  • "Hannah": Regardless of who goes first, Hannah will win the game.
  • "Victor": Regardless of who goes first, Victor will win the game.

For example, a position in which the only rectangle has dimensions 1x10 is a "Victor" position. (If Hannah goes first, she has no valid move and she loses the game. If Victor goes first, he breaks the rectangle arbitrarily and then Hannah loses the game as before.)

A position with a 2x1 rectangle and a 1x2 rectangle is a "second" position: whoever goes first breaks the one rectangle they can break into two 1x1 squares, then their opponent breaks the other rectangle, and then the person who went first loses the game.

A position with a 3x1 rectangle and a 1x2 rectangle is a "Hannah" position.


Given a position P and a type T, let MINR(P,T) be the smallest R >= 2 such that the position obtained from P by adding a Rx1 rectangle has type T.

Similarly, let MINC(P,T) be the smallest C >= 2 such that the position obtained from P by adding a 1xC rectangle has type T.

If such an R or C does not exist, we say that the corresponding MINR or MINC value is zero.

For example, if P is the position that consists just of a single 3x1 rectangle, then MINC(P,second) = 3 because {3x1, 1x2} is a "Hannah" position but {3x1, 1x3} is clearly a "second" position.


You are given a position P. For each valid i, this position contains a rectangle of dimensions posR[i] x posC[i].

Return a int[] with 8 elements: { MINR(P,first), MINR(P,second), MINR(P,Hannah), MINR(P,Victor), MINC(P,first), MINC(P,second), MINC(P,Hannah), MINC(P,Victor) }.

Definition

Class:
RectangleBreaking
Method:
solve
Parameters:
int[], int[]
Returns:
int[]
Method signature:
int[] solve(int[] posR, int[] posC)
(be sure your method is public)

Notes

  • It is guaranteed that for the given constraints the answers always fit into 32-bit signed ints.

Constraints

  • posR will contain between 1 and 10 elements, inclusive.
  • posC will contain the same number of elements as posR.
  • Each number in the input will be between 1 and 10^8, inclusive.

Examples

  1. {3}

    {1}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

    If we add any Rx1 rectangle, we will have a "Hannah" position: Victor loses as soon as it's his turn. The smallest such rectangle is 2x1. If we add a 1x2 rectangle, we will have a "Hannah" position as explained above. If we add a 1x3 rectangle, we will have a "second" position. If we add a 1xC rectangle with C >=4, we will have a "Victor" position. The 1x4 rectangle is the smallest one of these. As we exhausted all the options for what to add, no other position types can be reached.

  2. {47}

    {46}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  3. {4, 7, 23}

    {7, 4, 23}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  4. {1, 3, 6}

    {2, 6, 5}

    Returns: {0, 4, 5, 2, 0, 0, 0, 2 }

  5. {1, 7}

    {2, 7}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  6. {4, 2}

    {4, 1}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  7. {1}

    {2}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  8. {1}

    {3}

    Returns: {0, 3, 4, 2, 0, 0, 0, 2 }

  9. {1}

    {4}

    Returns: {0, 4, 5, 2, 0, 0, 0, 2 }

  10. {1}

    {5}

    Returns: {0, 5, 6, 2, 0, 0, 0, 2 }

  11. {1}

    {6}

    Returns: {0, 6, 7, 2, 0, 0, 0, 2 }

  12. {2}

    {3}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  13. {2}

    {4}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  14. {2}

    {5}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  15. {2}

    {6}

    Returns: {0, 3, 4, 2, 0, 0, 0, 2 }

  16. {2}

    {7}

    Returns: {0, 3, 4, 2, 0, 0, 0, 2 }

  17. {3}

    {1}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  18. {3}

    {2}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  19. {3}

    {3}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  20. {3}

    {4}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  21. {3}

    {5}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  22. {3}

    {6}

    Returns: {0, 3, 4, 2, 0, 0, 0, 2 }

  23. {3}

    {7}

    Returns: {0, 3, 4, 2, 0, 0, 0, 2 }

  24. {4}

    {1}

    Returns: {0, 0, 2, 0, 0, 4, 2, 5 }

  25. {4}

    {2}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  26. {4}

    {3}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  27. {4}

    {4}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  28. {4}

    {5}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  29. {4}

    {6}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  30. {4}

    {7}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  31. {5}

    {1}

    Returns: {0, 0, 2, 0, 0, 5, 2, 6 }

  32. {5}

    {2}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  33. {5}

    {3}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  34. {5}

    {4}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  35. {5}

    {5}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  36. {5}

    {6}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  37. {5}

    {7}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  38. {6}

    {1}

    Returns: {0, 0, 2, 0, 0, 6, 2, 7 }

  39. {6}

    {2}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  40. {6}

    {3}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  41. {6}

    {4}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  42. {6}

    {5}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  43. {6}

    {6}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  44. {6}

    {7}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  45. {7}

    {1}

    Returns: {0, 0, 2, 0, 0, 7, 2, 8 }

  46. {7}

    {2}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  47. {7}

    {3}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  48. {7}

    {4}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  49. {7}

    {5}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  50. {7}

    {6}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  51. {7}

    {7}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  52. {12}

    {3}

    Returns: {0, 0, 2, 0, 0, 6, 2, 7 }

  53. {14}

    {18}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  54. {15}

    {19}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  55. {11}

    {9}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  56. {17}

    {13}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  57. {13}

    {20}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  58. {2}

    {14}

    Returns: {0, 7, 8, 2, 0, 0, 0, 2 }

  59. {1}

    {4}

    Returns: {0, 4, 5, 2, 0, 0, 0, 2 }

  60. {1}

    {9}

    Returns: {0, 9, 10, 2, 0, 0, 0, 2 }

  61. {16}

    {18}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  62. {2}

    {41}

    Returns: {0, 20, 21, 2, 0, 0, 0, 2 }

  63. {73}

    {55}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  64. {30}

    {31}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  65. {67}

    {66}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  66. {46}

    {57}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  67. {31}

    {5}

    Returns: {0, 0, 2, 0, 0, 7, 2, 8 }

  68. {72}

    {48}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  69. {92}

    {89}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  70. {46}

    {77}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  71. {44}

    {72}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  72. {5}

    {93}

    Returns: {0, 23, 24, 2, 0, 0, 0, 2 }

  73. {2}

    {90}

    Returns: {0, 45, 46, 2, 0, 0, 0, 2 }

  74. {2}

    {95}

    Returns: {0, 47, 48, 2, 0, 0, 0, 2 }

  75. {1}

    {95}

    Returns: {0, 95, 96, 2, 0, 0, 0, 2 }

  76. {5}

    {96}

    Returns: {0, 24, 25, 2, 0, 0, 0, 2 }

  77. {5}

    {98}

    Returns: {0, 24, 25, 2, 0, 0, 0, 2 }

  78. {3}

    {91}

    Returns: {0, 45, 46, 2, 0, 0, 0, 2 }

  79. {2}

    {95}

    Returns: {0, 47, 48, 2, 0, 0, 0, 2 }

  80. {2}

    {97}

    Returns: {0, 48, 49, 2, 0, 0, 0, 2 }

  81. {1}

    {96}

    Returns: {0, 96, 97, 2, 0, 0, 0, 2 }

  82. {447243}

    {1649029}

    Returns: {0, 6, 7, 2, 0, 0, 0, 2 }

  83. {25554709}

    {1106}

    Returns: {0, 0, 2, 0, 0, 24955, 2, 24956 }

  84. {26614}

    {234744}

    Returns: {0, 14, 15, 2, 0, 0, 0, 2 }

  85. {184}

    {321879}

    Returns: {0, 2514, 2515, 2, 0, 0, 0, 2 }

  86. {741433}

    {4036}

    Returns: {0, 0, 2, 0, 0, 362, 2, 363 }

  87. {166}

    {8440}

    Returns: {0, 65, 66, 2, 0, 0, 0, 2 }

  88. {18}

    {3}

    Returns: {0, 0, 2, 0, 0, 9, 2, 10 }

  89. {63996}

    {31393960}

    Returns: {0, 958, 959, 2, 0, 0, 0, 2 }

  90. {1091}

    {401087}

    Returns: {0, 391, 392, 2, 0, 0, 0, 2 }

  91. {35046489}

    {194778}

    Returns: {0, 0, 2, 0, 0, 267, 2, 268 }

  92. {4, 7}

    {6, 3}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  93. {3, 4}

    {8, 3}

    Returns: {0, 3, 4, 2, 0, 0, 0, 2 }

  94. {2, 6}

    {3, 7}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  95. {2, 8}

    {5, 1}

    Returns: {0, 0, 2, 0, 0, 7, 2, 8 }

  96. {2, 2}

    {7, 6}

    Returns: {0, 5, 6, 2, 0, 0, 0, 2 }

  97. {1, 1}

    {5, 3}

    Returns: {0, 7, 8, 2, 0, 0, 0, 2 }

  98. {3, 4}

    {8, 8}

    Returns: {0, 5, 6, 2, 0, 0, 0, 2 }

  99. {8, 2}

    {1, 3}

    Returns: {0, 0, 2, 0, 0, 8, 2, 9 }

  100. {3, 1}

    {6, 4}

    Returns: {0, 6, 7, 2, 0, 0, 0, 2 }

  101. {1, 2}

    {7, 1}

    Returns: {0, 6, 7, 2, 0, 0, 0, 2 }

  102. {2, 1}

    {5, 5}

    Returns: {0, 6, 7, 2, 0, 0, 0, 2 }

  103. {4, 5}

    {3, 2}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  104. {8, 1}

    {6, 2}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  105. {7, 6}

    {7, 5}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  106. {8, 2}

    {3, 2}

    Returns: {0, 0, 2, 0, 0, 4, 2, 5 }

  107. {8, 1}

    {8, 7}

    Returns: {0, 7, 8, 2, 0, 0, 0, 2 }

  108. {2, 8}

    {5, 2}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  109. {4, 6}

    {6, 3}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  110. {8, 2}

    {1, 8}

    Returns: {0, 0, 2, 0, 0, 5, 2, 6 }

  111. {8, 1}

    {5, 4}

    Returns: {0, 3, 4, 2, 0, 0, 0, 2 }

  112. {52818346, 128802}

    {1, 2328}

    Returns: {0, 0, 2, 0, 0, 52818407, 2, 52818408 }

  113. {5108953, 212781}

    {112979, 5774}

    Returns: {0, 0, 2, 0, 0, 127, 2, 128 }

  114. {4961404, 3410}

    {52756, 112737}

    Returns: {0, 0, 2, 0, 0, 97, 2, 98 }

  115. {81711621, 1126}

    {39807665, 1139}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  116. {805215, 363}

    {181, 13099}

    Returns: {0, 0, 2, 0, 0, 6240, 2, 6241 }

  117. {15408, 15}

    {568, 7843}

    Returns: {0, 951, 952, 2, 0, 0, 0, 2 }

  118. {61464, 308}

    {397264, 319}

    Returns: {0, 12, 13, 2, 0, 0, 0, 2 }

  119. {6853, 50010}

    {30343, 535}

    Returns: {0, 0, 2, 0, 0, 91, 2, 92 }

  120. {356253, 36426437}

    {1839232, 21}

    Returns: {0, 0, 2, 0, 0, 2276646, 2, 2276647 }

  121. {303003, 1}

    {29852, 11074}

    Returns: {0, 11057, 11058, 2, 0, 0, 0, 2 }

  122. {335067, 116537}

    {4804879, 4093}

    Returns: {0, 0, 2, 0, 0, 39, 2, 40 }

  123. {8012159, 5221776}

    {915616, 59014}

    Returns: {0, 0, 2, 0, 0, 173, 2, 174 }

  124. {4, 4950}

    {30879824, 90574277}

    Returns: {0, 7742067, 7742068, 2, 0, 0, 0, 2 }

  125. {30777, 3389}

    {311282, 5706}

    Returns: {0, 19, 20, 2, 0, 0, 0, 2 }

  126. {918, 15}

    {77120154, 619}

    Returns: {0, 150701, 150702, 2, 0, 0, 0, 2 }

  127. {252, 1084}

    {19888029, 2381}

    Returns: {0, 155376, 155377, 2, 0, 0, 0, 2 }

  128. {379709, 49655}

    {46581, 3383016}

    Returns: {0, 93, 94, 2, 0, 0, 0, 2 }

  129. {40221, 24291}

    {346, 3989}

    Returns: {0, 0, 2, 0, 0, 167, 2, 168 }

  130. {235819, 916560}

    {385483, 20357974}

    Returns: {0, 39, 40, 2, 0, 0, 0, 2 }

  131. {577, 87}

    {19, 2}

    Returns: {0, 0, 2, 0, 0, 78, 2, 79 }

  132. {21, 14, 368, 9900238, 4}

    {2, 7, 1776112, 853703, 40}

    Returns: {0, 6918, 6919, 2, 0, 0, 0, 2 }

  133. {54984225, 55846, 984740, 8310258}

    {15585482, 31054619, 7480, 52}

    Returns: {0, 0, 2, 0, 0, 258993, 2, 258994 }

  134. {486815, 6, 703}

    {10224, 4579, 31948}

    Returns: {0, 1147, 1148, 2, 0, 0, 0, 2 }

  135. {40600, 130229, 1392131, 2, 1}

    {33, 657, 13238476, 6699986, 216}

    Returns: {0, 3348699, 3348700, 2, 0, 0, 0, 2 }

  136. {93724, 11, 26897538}

    {1783, 280252, 419212}

    Returns: {0, 34840, 34841, 2, 0, 0, 0, 2 }

  137. {7, 2043, 98, 70330243}

    {61626879, 1, 2287, 2829}

    Returns: {0, 15370372, 15370373, 2, 0, 0, 0, 2 }

  138. {1205, 9302, 2, 22854}

    {1718, 25126, 46, 259}

    Returns: {0, 0, 2, 0, 0, 65, 2, 66 }

  139. {268363, 114382, 922}

    {182, 23404, 1918307}

    Returns: {0, 1646, 1647, 2, 0, 0, 0, 2 }

  140. {28344260, 280, 33779967, 3948}

    {4, 376792, 1, 37}

    Returns: {0, 0, 2, 0, 0, 40864683, 2, 40864684 }

  141. {55565, 415, 14856, 4948705}

    {1, 1, 6984477, 235}

    Returns: {0, 0, 2, 0, 0, 93788, 2, 93789 }

  142. {3680048, 271, 11, 7599}

    {2770, 181243, 2, 7561}

    Returns: {0, 0, 2, 0, 0, 1094, 2, 1095 }

  143. {5264526, 125839, 2, 42162297, 9}

    {14, 165, 194372, 2, 41109}

    Returns: {0, 0, 2, 0, 0, 21637872, 2, 21637873 }

  144. {240731, 274443, 82850349, 516071, 7780}

    {129508, 20, 12, 13258, 358341}

    Returns: {0, 0, 2, 0, 0, 10373421, 2, 10373422 }

  145. {8088, 895, 27088480}

    {29754, 105105, 3590}

    Returns: {0, 0, 2, 0, 0, 13016, 2, 13017 }

  146. {403032, 2463, 139971}

    {15, 40778320, 1720}

    Returns: {0, 0, 2, 0, 0, 30604, 2, 30605 }

  147. {1357890, 17, 26983, 930, 43}

    {217, 30612309, 12, 1282486, 383000}

    Returns: {0, 1913761, 1913762, 2, 0, 0, 0, 2 }

  148. {1563839, 5, 107530, 25138065}

    {13777, 190710, 740238, 1803}

    Returns: {0, 22951, 22952, 2, 0, 0, 0, 2 }

  149. {21963, 27092, 152}

    {2267, 75320, 11}

    Returns: {0, 0, 2, 0, 0, 25, 2, 26 }

  150. {466350, 219, 1484, 141119}

    {82005619, 7, 384, 11869171}

    Returns: {0, 344, 345, 2, 0, 0, 0, 2 }

  151. {13520, 10, 6, 12927680}

    {10304874, 792, 34, 375945}

    Returns: {0, 1314, 1315, 2, 0, 0, 0, 2 }

  152. {2081104, 2143, 7}

    {18921, 681472, 368}

    Returns: {0, 297, 298, 2, 0, 0, 0, 2 }

  153. {11572765, 758654, 120492, 1267}

    {2, 77237, 417, 3}

    Returns: {0, 0, 2, 0, 0, 5787493, 2, 5787494 }

  154. {39, 110187, 24123310, 450}

    {615138, 16513003, 1, 143}

    Returns: {0, 0, 2, 0, 0, 24103840, 2, 24103841 }

  155. {245, 64575, 6134}

    {47202, 419, 434424}

    Returns: {0, 222, 223, 2, 0, 0, 0, 2 }

  156. {744205, 47, 3189925, 856, 6943923}

    {90928320, 9084991, 6666400, 44159, 1402}

    Returns: {0, 277384, 277385, 2, 0, 0, 0, 2 }

  157. {2083376, 3949, 33296648}

    {2, 304, 25852988}

    Returns: {0, 0, 2, 0, 0, 1041702, 2, 1041703 }

  158. {367, 3, 982, 87}

    {62242496, 462712, 338, 1495}

    Returns: {0, 474509, 474510, 2, 0, 0, 0, 2 }

  159. {1, 1042, 234, 15634}

    {4083845, 822489, 12349177, 1}

    Returns: {0, 4165490, 4165491, 2, 0, 0, 0, 2 }

  160. {14, 69, 78605, 124302, 44375665}

    {11258, 3900, 69008, 129170, 23}

    Returns: {0, 0, 2, 0, 0, 2772014, 2, 2772015 }

  161. {1716530, 50773, 631, 24360318}

    {63, 12376, 12653955, 1}

    Returns: {0, 0, 2, 0, 0, 24389250, 2, 24389251 }

  162. {3975782, 733, 25509617}

    {4905416, 608, 43062}

    Returns: {0, 0, 2, 0, 0, 777, 2, 778 }

  163. {1309, 2, 91208529, 277}

    {5575301, 37298731, 315974, 27533566}

    Returns: {0, 18762013, 18762014, 2, 0, 0, 0, 2 }

  164. {3, 356, 337639}

    {153, 260816, 10674647}

    Returns: {0, 1132, 1133, 2, 0, 0, 0, 2 }

  165. {3105770, 244, 352}

    {425974, 17659385, 4407659}

    Returns: {0, 155169, 155170, 2, 0, 0, 0, 2 }

  166. {24, 1530, 22695393, 52}

    {60, 2781, 17, 473217}

    Returns: {0, 0, 2, 0, 0, 1403672, 2, 1403673 }

  167. {393, 373, 101, 21, 32217379}

    {621633, 1, 64188134, 105219, 405}

    Returns: {0, 885721, 885722, 2, 0, 0, 0, 2 }

  168. {4628683, 1192392, 242479, 2966, 3963473}

    {54134919, 471695, 14, 59871, 89443}

    Returns: {0, 0, 2, 0, 0, 30332, 2, 30333 }

  169. {3360, 9, 94, 28087148}

    {3831, 7831989, 134, 3288}

    Returns: {0, 965286, 965287, 2, 0, 0, 0, 2 }

  170. {48, 86, 1195, 199, 35}

    {2, 446999, 2095437, 14562747, 51032612}

    Returns: {0, 1717544, 1717545, 2, 0, 0, 0, 2 }

  171. {77, 28, 51135, 26}

    {52799, 179, 11080419, 12}

    Returns: {0, 1169, 1170, 2, 0, 0, 0, 2 }

  172. {1}

    {1}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  173. {1,1,1,1,1,1}

    {1,1,1,1,1,1}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  174. {5, 30, 17, 26, 27, 7, 17}

    {28, 22, 25, 3, 2, 1, 31}

    Returns: {0, 0, 2, 0, 0, 25, 2, 26 }

  175. {1, 28, 16, 29, 3, 23, 13, 3, 22, 24}

    {21, 15, 23, 16, 24, 22, 16, 9, 7, 25}

    Returns: {0, 30, 31, 2, 0, 0, 0, 2 }

  176. {17, 15, 14, 8, 23, 16, 23, 31, 26, 15}

    {7, 22, 31, 27, 19, 17, 3, 20, 17, 8}

    Returns: {0, 0, 2, 0, 0, 9, 2, 10 }

  177. {25, 17, 29, 11, 5}

    {32, 10, 1, 6, 18}

    Returns: {0, 0, 2, 0, 0, 27, 2, 28 }

  178. {31, 24, 17, 21, 16, 23, 12, 31, 9, 9}

    {28, 3, 31, 2, 14, 28, 12, 13, 7, 23}

    Returns: {0, 0, 2, 0, 0, 24, 2, 25 }

  179. {26, 18, 1, 27, 24, 17, 9, 32, 32, 1}

    {7, 29, 8, 5, 2, 3, 12, 13, 30, 5}

    Returns: {0, 0, 2, 0, 0, 22, 2, 23 }

  180. {10, 3, 4, 8}

    {22, 16, 25, 2}

    Returns: {0, 11, 12, 2, 0, 0, 0, 2 }

  181. {20, 20, 10}

    {4, 16, 18}

    Returns: {0, 0, 2, 0, 0, 4, 2, 5 }

  182. {32, 4, 27}

    {22, 8, 27}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  183. {20, 9, 8, 30, 28, 19, 8}

    {32, 5, 30, 2, 5, 32, 16}

    Returns: {0, 0, 2, 0, 0, 17, 2, 18 }

  184. {22, 30, 7, 30, 2, 19, 17}

    {11, 2, 30, 18, 13, 3, 31}

    Returns: {0, 0, 2, 0, 0, 13, 2, 14 }

  185. {5, 31, 20, 14, 7, 26, 24, 6}

    {7, 24, 27, 6, 20, 22, 7, 28}

    Returns: {0, 4, 5, 2, 0, 0, 0, 2 }

  186. {4, 4, 18, 14, 14, 20, 29}

    {23, 26, 17, 19, 30, 29, 21}

    Returns: {0, 13, 14, 2, 0, 0, 0, 2 }

  187. {10, 1}

    {31, 2}

    Returns: {0, 4, 5, 2, 0, 0, 0, 2 }

  188. {30, 17, 7, 8, 28, 32, 16, 21}

    {29, 19, 20, 11, 22, 28, 17, 2}

    Returns: {0, 0, 2, 0, 0, 7, 2, 8 }

  189. {30, 25, 12, 5, 27, 15, 12, 1}

    {12, 3, 12, 32, 4, 30, 26, 9}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  190. {25, 25, 30}

    {1, 32, 24}

    Returns: {0, 0, 2, 0, 0, 24, 2, 25 }

  191. {26, 6, 27}

    {7, 27, 7}

    Returns: {0, 0, 2, 0, 0, 6, 2, 7 }

  192. {32, 29, 26, 28}

    {31, 6, 21, 13}

    Returns: {0, 0, 2, 0, 0, 10, 2, 11 }

  193. {26, 9, 22, 17, 6, 2, 6}

    {5, 32, 7, 32, 23, 26, 15}

    Returns: {0, 14, 15, 2, 0, 0, 0, 2 }

  194. {14, 20, 4, 12, 16, 31, 26, 24, 22, 11}

    {17, 8, 19, 32, 26, 1, 16, 7, 5, 7}

    Returns: {0, 0, 2, 0, 0, 35, 2, 36 }

  195. {12, 10, 11, 6, 26}

    {6, 11, 5, 9, 23}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  196. {27, 15, 6}

    {19, 23, 21}

    Returns: {0, 6, 7, 2, 0, 0, 0, 2 }

  197. {3, 9, 6}

    {13, 22, 21}

    Returns: {0, 11, 12, 2, 0, 0, 0, 2 }

  198. {23, 29, 27, 2, 21, 28, 29, 7}

    {28, 28, 32, 13, 4, 7, 8, 22}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  199. {4, 12, 31, 8, 13, 32, 10, 19}

    {22, 27, 31, 15, 2, 21, 11, 5}

    Returns: {0, 0, 2, 0, 0, 4, 2, 5 }

  200. {20, 1}

    {3, 17}

    Returns: {0, 8, 9, 2, 0, 0, 0, 2 }

  201. {13, 24, 9, 29, 20, 27, 28}

    {14, 24, 13, 3, 20, 8, 27}

    Returns: {0, 0, 2, 0, 0, 16, 2, 17 }

  202. {32, 3, 15, 26, 2, 13, 24}

    {17, 32, 18, 4, 26, 27, 6}

    Returns: {0, 20, 21, 2, 0, 0, 0, 2 }

  203. {22, 5, 31, 5, 14, 28, 13}

    {29, 5, 18, 11, 15, 31, 19}

    Returns: {0, 3, 4, 2, 0, 0, 0, 2 }

  204. {8, 17}

    {1, 14}

    Returns: {0, 0, 2, 0, 0, 9, 2, 10 }

  205. {24, 14, 26, 27, 23, 7, 20, 14, 3, 25}

    {31, 22, 3, 21, 1, 2, 4, 1, 4, 30}

    Returns: {0, 0, 2, 0, 0, 52, 2, 53 }

  206. {6, 26, 3, 20, 4}

    {18, 23, 5, 20, 29}

    Returns: {0, 11, 12, 2, 0, 0, 0, 2 }

  207. {27, 6, 27, 7, 25, 19, 2, 9, 6}

    {22, 17, 24, 25, 12, 2, 13, 15, 1}

    Returns: {0, 0, 2, 0, 0, 3, 2, 4 }

  208. {28, 28, 10, 30, 10, 3, 9, 2}

    {27, 9, 25, 17, 5, 16, 5, 9}

    Returns: {0, 9, 10, 2, 0, 0, 0, 2 }

  209. {9, 27, 2}

    {19, 32, 11}

    Returns: {0, 7, 8, 2, 0, 0, 0, 2 }

  210. {10, 8, 19, 32, 20, 29, 1, 32, 27, 24}

    {15, 10, 31, 30, 27, 12, 28, 32, 22, 20}

    Returns: {0, 25, 26, 2, 0, 0, 0, 2 }

  211. {26, 3, 10, 26, 7, 24}

    {25, 18, 30, 7, 3, 22}

    Returns: {0, 4, 5, 2, 0, 0, 0, 2 }

  212. {1, 23, 3, 31}

    {17, 11, 27, 21}

    Returns: {0, 28, 29, 2, 0, 0, 0, 2 }

  213. {18, 22, 8, 12}

    {17, 27, 14, 15}

    Returns: {0, 0, 2, 0, 0, 0, 0, 2 }

  214. {16, 22, 24, 10, 15, 14}

    {30, 10, 8, 12, 21, 16}

    Returns: {0, 0, 2, 0, 0, 2, 0, 3 }

  215. {24, 12}

    {25, 32}

    Returns: {0, 4, 5, 2, 0, 0, 0, 2 }

  216. {13, 4, 21, 17}

    {26, 31, 5, 7}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  217. {14, 25, 17, 8}

    {18, 8, 23, 25}

    Returns: {0, 2, 3, 0, 0, 0, 0, 2 }

  218. {15, 17, 3, 19, 21, 10, 17}

    {19, 21, 14, 29, 8, 12, 22}

    Returns: {0, 7, 8, 2, 0, 0, 0, 2 }

  219. {7, 14, 18, 13, 32, 25}

    {19, 3, 14, 32, 5, 2}

    Returns: {0, 0, 2, 0, 0, 20, 2, 21 }

  220. {7, 20, 27, 6}

    {27, 15, 13, 14}

    Returns: {0, 5, 6, 2, 0, 0, 0, 2 }

  221. {6, 20, 24, 6, 30}

    {27, 21, 8, 21, 14}

    Returns: {0, 6, 7, 2, 0, 0, 0, 2 }

  222. {6, 31, 4}

    {22, 15, 21}

    Returns: {0, 7, 8, 2, 0, 0, 0, 2 }

  223. {25, 4, 17, 15, 19, 28}

    {17, 5, 30, 32, 21, 16}

    Returns: {0, 4, 5, 2, 0, 0, 0, 2 }

  224. {7 }

    {87654321 }

    Returns: {0, 21913580, 21913581, 2, 0, 0, 0, 2 }

  225. {829414, 38225584, 9670548, 62116444, 50739804, 46191558, 11418030, 53437514, 60174967, 8228360 }

    {56491527, 58306600, 44327450, 98869796, 40355195, 18710135, 10439154, 83488419, 58537053, 9985986 }

    Returns: {0, 113, 114, 2, 0, 0, 0, 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: