Statistics

Problem Statement for "FivePileSpecial"

Problem Statement

Five Pile Special is a NIM variant: a two-player combinatorial game. It is played with five piles of tokens, arranged in a row.

There are three types of valid moves:

  1. The player selects one of the piles, selects a positive number x, and removes x tokens from the selected pile.
  2. The player selects three consecutive piles, selects a positive number x, and removes x tokens from each of the selected piles.
  3. The player selects all five piles, selects a positive number x, and removes x tokens from each of the selected piles.

The players take alternating turns. The player unable to make a valid move loses the game.

You are given a position in this game: the long[] piles containing the token counts on the individual piles.

Each move in this game can be represented as a sequence of five values: for each pile, the number of tokens removed from it. Find all winning moves for the given position and return their concatenation (in any order).

Definition

Class:
FivePileSpecial
Method:
findWinningMoves
Parameters:
long[]
Returns:
long[]
Method signature:
long[] findWinningMoves(long[] piles)
(be sure your method is public)

Notes

  • An empty pile still counts as a pile. For example, if the token counts are {1, 0, 2, 3, 0}, the three non-empty piles are not consecutive.
  • You may assume that for each position that matches the constraints given below there are at most 1,000 distinct winning moves.

Constraints

  • piles will contain exactly 5 elements.
  • Each element of piles will be between 0 and 10^18, inclusive.

Examples

  1. {0, 0, 0, 7, 7}

    Returns: { }

    As most of the piles are empty, valid moves in this situation must only involve a single pile. Then, this is clearly a losing position: the second player can win by "mirroring" the first player's moves on the other pile.

  2. {7, 7, 7, 7, 7}

    Returns: {7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 7, 7, 7, 0, 0, 0, 7, 7, 7, 0, 0, 0, 7, 7, 7, 7, 7, 7, 7, 7 }

    Taking 7 from all piles is a winning move: the opponent has no tokens left and loses immediately. Taking 7 from the first three piles is also a winning move: it produces the situation from Example 0. Further analysis can show that taking 7 from any other valid set of piles is also a winning move.

  3. {47, 42, 0, 42, 47}

    Returns: { }

    A less trivial symmetric position that is losing for the same reason as in Example 0.

  4. {10, 0, 11, 0, 12}

    Returns: {3, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 11 }

    We can emulate a traditional game of three-pile NIM.

  5. {0, 11, 14, 19, 0}

    Returns: {0, 0, 0, 14, 0, 0, 6, 6, 6, 0 }

  6. {1, 2, 3, 4, 5}

    Returns: {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 3, 3, 3 }

  7. {0, 1234567890123, 0, 0, 2}

    Returns: {0, 1234567890121, 0, 0, 0 }

  8. {3, 18, 19, 9, 13}

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

  9. {0, 0, 0, 18, 0}

    Returns: {0, 0, 0, 18, 0 }

  10. {8, 0, 15, 0, 12}

    Returns: {5, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 5 }

  11. {18, 0, 0, 4, 19}

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

  12. {17, 4, 0, 0, 0}

    Returns: {13, 0, 0, 0, 0 }

  13. {10, 0, 12, 0, 19}

    Returns: {0, 0, 0, 0, 13 }

  14. {9, 0, 0, 16, 20}

    Returns: {5, 0, 0, 0, 0 }

  15. {0, 0, 0, 17, 14}

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

  16. {2, 20, 11, 0, 0}

    Returns: {0, 11, 0, 0, 0 }

  17. {14, 0, 7, 0, 0}

    Returns: {7, 0, 0, 0, 0 }

  18. {17, 4, 15, 0, 3}

    Returns: {9, 0, 0, 0, 0, 3, 3, 3, 0, 0 }

  19. {1, 2, 0, 7, 17}

    Returns: {0, 0, 0, 0, 13 }

  20. {19, 0, 0, 2, 0}

    Returns: {17, 0, 0, 0, 0 }

  21. {4, 0, 2, 8, 0}

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

  22. {20, 0, 11, 0, 14}

    Returns: {15, 0, 0, 0, 0 }

  23. {10, 20, 0, 0, 1}

    Returns: {0, 9, 0, 0, 0 }

  24. {19, 0, 17, 0, 11}

    Returns: {0, 0, 0, 0, 9 }

  25. {0, 0, 0, 9, 0}

    Returns: {0, 0, 0, 9, 0 }

  26. {0, 0, 13, 0, 18}

    Returns: {0, 0, 0, 0, 5 }

  27. {19, 14, 0, 0, 13}

    Returns: {16, 0, 0, 0, 0 }

  28. {18, 4, 0, 12, 0}

    Returns: {10, 0, 0, 0, 0 }

  29. {0, 9, 0, 0, 15}

    Returns: {0, 0, 0, 0, 6 }

  30. {11, 0, 1, 0, 17}

    Returns: {0, 0, 0, 0, 7 }

  31. {20, 10, 0, 0, 11}

    Returns: {19, 0, 0, 0, 0 }

  32. {14, 0, 11, 0, 20}

    Returns: {0, 0, 0, 0, 15 }

  33. {20, 0, 0, 0, 0}

    Returns: {20, 0, 0, 0, 0 }

  34. {2, 0, 0, 1, 0}

    Returns: {1, 0, 0, 0, 0 }

  35. {1, 16, 12, 0, 4}

    Returns: {0, 7, 0, 0, 0, 1, 1, 1, 0, 0 }

  36. {0, 18, 0, 0, 15}

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

  37. {0, 14, 0, 3, 0}

    Returns: {0, 11, 0, 0, 0 }

  38. {4, 16, 0, 0, 0}

    Returns: {0, 12, 0, 0, 0 }

  39. {0, 0, 10, 0, 0}

    Returns: {0, 0, 10, 0, 0 }

  40. {0, 0, 1, 20, 0}

    Returns: {0, 0, 0, 19, 0 }

  41. {4, 3, 0, 0, 0}

    Returns: {1, 0, 0, 0, 0 }

  42. {0, 0, 0, 0, 12}

    Returns: {0, 0, 0, 0, 12 }

  43. {0, 18, 0, 0, 0}

    Returns: {0, 18, 0, 0, 0 }

  44. {0, 0, 0, 17, 17}

    Returns: { }

  45. {15, 14, 1, 0, 0}

    Returns: { }

  46. {4, 19, 0, 14, 0}

    Returns: {0, 9, 0, 0, 0 }

  47. {0, 17, 17, 0, 0}

    Returns: { }

  48. {569053293246432485, 778675097473555940, 892478871779154367, 83691673841880157, 860750887004780211}

    Returns: {0, 680647829501081136, 0, 0, 0, 0, 0, 320359636023145936, 0, 0, 0, 0, 0, 0, 833680941639772624 }

  49. {344378353065206363, 740096584109370009, 983077373430527200, 7265889243685150, 397373807005081995}

    Returns: {165396193138475887, 0, 0, 0, 0, 0, 0, 183632693122542729, 0, 0, 0, 0, 0, 0, 163357851078132815 }

  50. {221620221863893416, 247946029137524918, 154041718082449964, 710425053384720529, 918239449410143008}

    Returns: {0, 0, 0, 0, 81959695957487485 }

  51. {938350855854213439, 347731646140784058, 771906763569383315, 486274708186176648, 487257357237951141}

    Returns: {0, 0, 75440304004855019, 0, 0, 0, 0, 0, 79932766716367573, 0, 0, 0, 0, 0, 64182400087952135, 0, 0, 64182739445543149, 64182739445543149, 64182739445543149 }

  52. {482280975052911520, 872515323410383247, 52336806124795462, 651340065655204282, 794878074541050211}

    Returns: {0, 582762387394813008, 0, 0, 0, 0, 0, 0, 573474282276101296, 0, 0, 0, 0, 0, 571565375437429648 }

  53. {565846813994758917, 311949145051972289, 67416862141501395, 27671438654171693, 219908494816654468}

    Returns: {1544710801219402, 0, 0, 0, 0, 0, 0, 4080390718791782, 0, 0, 0, 0, 0, 0, 2676932749123658, 4081627724996966, 4081627724996966, 4081627724996966, 0, 0, 0, 13087658814529942, 13087658814529942, 13087658814529942, 0 }

  54. {481120319935874744, 599751605610940370, 397932113379592283, 723565610790280330, 508681252090996056}

    Returns: {421818984938066013, 0, 0, 0, 0, 0, 0, 111290015362830243, 0, 0, 0, 0, 0, 0, 404864567789752221, 0, 228313941573365811, 228313941573365811, 228313941573365811, 0, 0, 0, 114035084117405731, 114035084117405731, 114035084117405731 }

  55. {964284062194801130, 75464421716246438, 545520533641992849, 74198193999274408, 187074928413061935}

    Returns: {603702455245120058, 0, 0, 0, 0 }

  56. {262210082172368209, 486646294279590261, 914633194886594857, 342087523134882183, 131648358329955775}

    Returns: {0, 0, 910262490495250701, 0, 0 }

  57. {650726718042103909, 13677429931848659, 614970606978891486, 613704450456360733, 543037958356684342}

    Returns: {95282194315103295, 0, 0, 0, 0, 0, 0, 166196298324800577, 0, 0, 0, 0, 0, 165915509544301503, 0 }

  58. {383258096159007576, 775927237081846359, 676160170224447778, 375218691335986303, 934954173405322239}

    Returns: {0, 343797632356105309, 0, 0, 0, 0, 0, 218576176946985619, 0, 0, 0, 0, 0, 0, 664173055638749101, 0, 0, 123717735964884883, 123717735964884883, 123717735964884883 }

  59. {619810633770784527, 126000278773846986, 358525861160498800, 56018828050579757, 252113861336213898}

    Returns: {115780062475602418, 0, 0, 0, 0 }

  60. {946775430259291198, 604405814612994019, 705488278031993338, 40252871599210469, 639473917759778914}

    Returns: {227890681125393056, 0, 0, 0, 0 }

  61. {56790306381658474, 534998970961277093, 103501385439599678, 319653937293492633, 778355950475553069}

    Returns: {0, 0, 0, 0, 587684448328455365 }

  62. {733049010439060831, 455899422092189830, 401059259403300688, 350536436202951711, 823547728049457131}

    Returns: {0, 452514889515687563, 0, 0, 0, 0, 0, 126496463397609763, 0, 0, 0, 0, 0, 169562160540163773, 0, 0, 240564309298006561, 240564309298006561, 240564309298006561, 0, 90538160125652577, 90538160125652577, 90538160125652577, 90538160125652577, 90538160125652577 }

  63. {59988196106834630, 534276238254437446, 839930098279903824, 383478584773683719, 103684198697542277}

    Returns: {0, 0, 579565619212846158, 0, 0 }

  64. {983369300793512351, 430615669170556784, 113244646514335146, 435103331410742535, 203399550996705446}

    Returns: {933588704372531748, 0, 0, 0, 0 }

  65. {34348602787789584, 663058584590709190, 779555371779616404, 936247845884300525, 145247703054338342}

    Returns: {0, 351834306160468343, 0, 0, 0, 0, 0, 224607754462076791, 0, 0, 0, 0, 0, 820243989620744073, 0, 0, 659207176328992117, 659207176328992117, 659207176328992117, 0 }

  66. {256875223220485671, 8781009467735276, 493028128177114875, 815216774895124104, 666749101350329828}

    Returns: {0, 0, 376119807195065684, 0, 0, 0, 0, 376460655866244236, 376460655866244236, 376460655866244236 }

  67. {147090272122686113, 891388345180737711, 853022070483593697, 854943794453232930, 433165623173104119}

    Returns: {0, 602122434527605018, 0, 0, 0, 0, 0, 597444820099941126, 0, 0, 0, 0, 0, 602693888378293002, 0, 0, 597734799111590174, 597734799111590174, 597734799111590174, 0 }

  68. {739469405044653114, 302803910832668847, 951371044481837128, 170128837079839550, 45680447849014219}

    Returns: {0, 0, 46437333921446888, 0, 0 }

  69. {278400431200181905, 842776151513987754, 147882010062883058, 157921034106632618, 597791291293913744}

    Returns: {6634359641064751, 0, 0, 0, 0, 0, 2091712252493137, 0, 0, 0, 0, 0, 0, 2091499660000081, 0, 2125247355124175, 2125247355124175, 2125247355124175, 0, 0, 0, 0, 2373485736672717, 2373485736672717, 2373485736672717 }

  70. {146747259053475507, 984893315645531671, 657105825466685349, 631070477289708244, 706125997454526804}

    Returns: {0, 257156231966991233, 0, 0, 0, 0, 176091447258324355, 176091447258324355, 176091447258324355, 0 }

  71. {669783931387042182, 27047500156249452, 901461658455183182, 689205326612620549, 666691287306352487}

    Returns: {0, 0, 182143803104518342, 0, 0, 0, 0, 227153393913290818, 227153393913290818, 227153393913290818 }

  72. {730179301812387455, 168164010156642700, 266587825193006759, 135218334470465355, 328743981921782135}

    Returns: {403133126943667560, 0, 0, 0, 0 }

  73. {558392703711330766, 930308203844032175, 564991620458512684, 950119992750993830, 697542489704972970}

    Returns: {0, 576452387077513921, 0, 0, 0, 0, 0, 0, 576397618191703231, 0, 0, 0, 0, 0, 576489907335355071 }

  74. {472374746653699296, 518479157482568709, 211539893686792232, 493389230085925928, 908571807768891203}

    Returns: {0, 0, 0, 0, 509052360180777566 }

  75. {564511854731415511, 470436270815274719, 432276455384053908, 348054883515236137, 454796343151112197}

    Returns: {428319055210970736, 0, 0, 0, 0, 0, 420609286106869360, 0, 0, 0, 0, 0, 159361116443611760, 0, 0, 0, 0, 0, 140084209592212880, 0, 0, 0, 0, 0, 420574086182306128, 419483034114019952, 419483034114019952, 419483034114019952, 0, 0, 0, 274924124942594448, 274924124942594448, 274924124942594448, 0, 0, 0, 275205605715640432, 275205605715640432, 275205605715640432 }

  76. {954347569311016895, 40994184556992980, 879686751750019834, 309818163942300346, 538837457874105050}

    Returns: {0, 0, 0, 0, 118082418346865839, 0, 0, 135808829903811759, 135808829903811759, 135808829903811759 }

  77. {116839866803885179, 760361187826642913, 683467620972663864, 424009689981829878, 736144663984447330}

    Returns: {0, 240725217105400330, 0, 0, 0, 0, 0, 339104430233988650, 0, 0, 0, 0, 0, 0, 192324036643762702, 0, 0, 108849201192121866, 108849201192121866, 108849201192121866 }

  78. {3783930143681864, 2850790508175, 0, 55787, 552}

    Returns: {3781079353118716, 0, 0, 0, 0 }

  79. {2054359330270643, 884204506, 392, 957807343382519916, 41039565}

    Returns: {0, 0, 0, 955752983335036736, 0 }

  80. {5542, 403208161494, 214932429898835729, 451469903, 496302607399578211}

    Returns: {0, 0, 0, 0, 281370374963106357 }

  81. {82, 209688201513913398, 10917054514, 843495657578242, 997840307421834822}

    Returns: {0, 0, 0, 0, 787849616317289202 }

  82. {774691139978383993, 1439426313, 399662224065222212, 18578037, 887755143}

    Returns: {375028916447311802, 0, 0, 0, 0 }

  83. {26090418971, 40, 13937633626442097, 206635126373, 18716195725}

    Returns: {0, 0, 13937417453617814, 0, 0 }

  84. {14633854, 1595722308530, 196854, 221513869, 181905240451591}

    Returns: {0, 0, 0, 0, 180309565837648 }

  85. {112787699958, 77944, 185598, 3, 383184348305}

    Returns: {0, 0, 0, 0, 270396868638 }

  86. {8755257967854, 14, 1428475319931, 58, 377659}

    Returns: {7326782467962, 0, 0, 0, 0 }

  87. {10559259516739029, 5926, 34326963726, 427485, 5190410}

    Returns: {10559225186211286, 0, 0, 0, 0 }

  88. {26, 382175789, 473252414659340, 277042562507987, 922073898846028}

    Returns: {0, 0, 0, 0, 546469289447780 }

  89. {460844, 36658, 12, 386685185, 4232015358}

    Returns: {0, 0, 0, 0, 3845361643 }

  90. {214568, 100501984, 459043157434, 49967795969, 24838402225379349}

    Returns: {0, 0, 0, 0, 24837984427319970 }

  91. {17744, 1, 111843564290348, 120584494886966995, 2894005358}

    Returns: {0, 0, 0, 120472653006083776, 0 }

  92. {122820292601771, 1345, 4371104635014, 8, 32353761}

    Returns: {118449160009597, 0, 0, 0, 0 }

  93. {547670133507275443, 155698, 867484471263633, 1640545, 16315763687420}

    Returns: {546796922757031029, 0, 0, 0, 0 }

  94. {12, 452614622939, 425165925, 759, 1766}

    Returns: {0, 452189458019, 0, 0, 0 }

  95. {13254, 2, 17130797649474, 1, 0}

    Returns: {0, 0, 17130797636221, 0, 0 }

  96. {851624959845, 31078676915, 296838702, 2624314835043912, 63501071199916}

    Returns: {0, 0, 0, 2561635762624500, 0 }

  97. {184466931, 17888, 31949062, 10839942456, 32403467975}

    Returns: {0, 0, 0, 0, 21447611034 }

  98. {11119356977, 107283, 4067, 3327484602, 405542780}

    Returns: {7386895099, 0, 0, 0, 0 }

  99. {1292952, 817396480021308, 2, 31060, 82299206692718}

    Returns: {0, 735097274492572, 0, 0, 0 }

  100. {750844, 622940, 875937779815213, 5364708, 81446171904605}

    Returns: {0, 0, 794491602595604, 0, 0 }

  101. {21713587758497019, 142074, 1543543903518506, 30, 78464}

    Returns: {20170043854788013, 0, 0, 0, 0 }

  102. {364567, 99369473918, 26630139337721, 8396514429310, 1821843635502296}

    Returns: {0, 0, 0, 0, 1787150595188458 }

  103. {151446039750557574, 90500299, 129356, 3885, 0}

    Returns: {151446039660045532, 0, 0, 0, 0 }

  104. {6269315, 22785674, 761531886987062, 1126, 6677}

    Returns: {0, 0, 761531869941180, 0, 0 }

  105. {438485392142, 8904, 22789277981, 250734, 1386}

    Returns: {415695953213, 0, 0, 0, 0 }

  106. {27746144694, 144646, 5121288362916586, 496495371072, 62303430401}

    Returns: {0, 0, 5120758249921017, 0, 0 }

  107. {449, 12149948, 6701160581, 13237872612998, 27525427}

    Returns: {0, 0, 0, 13231187483067, 0 }

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: