Statistics

Problem Statement for "SlowestNim"

Problem Statement

This problem is about the traditional game of NIM. To refresh your memory, the rules of NIM are as follows:

There are several piles of tokens. Two players take alternating turns. In each turn, the active player chooses one non-empty pile of tokens and removes some tokens from the pile. (The player can remove as many tokens as they like, but all tokens must be taken from the same pile and the player must always remove at least one token.) The player who cannot make a valid move (because all piles are already empty) loses the game.


You are playing NIM against your nemesis. It is your turn to play. The current pile sizes are given in the int[] piles.

Sadly, you noticed that you are in a losing position: if your nemesis will play optimally, you have no way to win the game. Even more sadly, you are sure that your nemesis knows the optimal strategy for the game of NIM, so there's no chance for you.


Or is there some chance after all? You still have one glimmer of hope: what if you drag the game out? Maybe your opponent will become tired and make a mistake. Thus, you set yourself a new goal: maximize the number of turns the game will take.

Your nemesis can read you like an open book and they immediately understand what's going on. They now want to disrupt your plan by not just winning, but by doing so in a way that requires as few moves as possible. We will assume that they play the game optimally with these goals in mind.


Return the int[] {A, B, C}, where A is the number of turns the game will take (assuming you both play optimally) and B, C describe one optimal move in the given situation: decrement piles[B] by C. If there are multiple optimal moves, you may return any one of them.

Definition

Class:
SlowestNim
Method:
move
Parameters:
int[]
Returns:
int[]
Method signature:
int[] move(int[] piles)
(be sure your method is public)

Constraints

  • piles will contain between 1 and 50 elements, inclusive.
  • Each element of piles will be between 1 and 20,000,000, inclusive.
  • piles will represent a losing position in the game of NIM.

Examples

  1. {10, 10}

    Returns: {20, 1, 1 }

    Here the optimal strategy for you is easy: just take one token from any pile, the opponent then has to take one token from the other pile, and so on. You will eventually lose, but at least it will take the full 20 moves.

  2. {1, 2, 3}

    Returns: {6, 2, 1 }

    Here you need to be careful, not all good-looking moves you can make in this position are optimal.

  3. {123, 456, 678, 789}

    Returns: {2046, 0, 1 }

  4. {1726, 56, 138, 134, 4, 1678}

    Returns: {3736, 0, 1 }

  5. {256, 128, 384}

    Returns: {768, 1, 1 }

  6. {27960, 6896, 30664}

    Returns: {65520, 0, 1 }

  7. {2105536, 5602432, 1643328, 7098112}

    Returns: {16449408, 0, 1 }

  8. {512, 3072, 512, 2048, 1536, 512}

    Returns: {8192, 0, 1 }

  9. {17408, 105984, 468992, 455168}

    Returns: {1047552, 1, 1 }

  10. {3474432, 6373120, 8143872, 2653952}

    Returns: {20645376, 1, 1 }

  11. {256, 256, 256, 256}

    Returns: {1024, 0, 1 }

  12. {15904, 1056, 14848}

    Returns: {31808, 0, 1 }

  13. {11136, 896, 1280, 11520}

    Returns: {24832, 0, 1 }

  14. {2, 4, 8, 4, 10}

    Returns: {28, 0, 1 }

  15. {2356166, 3039683, 8584198, 8237333, 15916822}

    Returns: {38134202, 1, 1 }

  16. {64, 64, 64, 64, 64, 64}

    Returns: {384, 0, 1 }

  17. {9191494, 5161771, 4011734, 8973921, 7822298}

    Returns: {35161218, 1, 1 }

  18. {9444896, 8241888, 5749824, 9336896, 3414208}

    Returns: {36187712, 0, 1 }

  19. {3, 2, 1, 3, 1, 2}

    Returns: {12, 0, 1 }

  20. {458752, 262144, 196608}

    Returns: {917504, 0, 1 }

  21. {7760512, 379072, 9860384, 1647296, 16577952}

    Returns: {36225216, 2, 1 }

  22. {16384, 278528, 507904, 1179648, 49152, 1114112}

    Returns: {3145728, 0, 1 }

  23. {184320, 75776, 2048, 26624, 235520}

    Returns: {524288, 1, 1 }

  24. {7149568, 6049792, 843776, 5869568, 9779200, 948224, 6576128, 4495360, 4268032, 3534848, 4861952, 3510272, 13944832}

    Returns: {71831552, 0, 1 }

  25. {24576, 16384, 8192, 8192, 24576, 24576, 16384, 16384, 8192, 24576, 16384, 24576, 8192, 16384, 16384, 8192, 8192, 16384, 8192, 8192, 8192, 8192, 8192, 24576, 16384, 16384, 8192, 16384, 8192, 24576, 8192, 24576, 8192, 16384, 8192, 16384, 24576, 8192, 8192, 8192, 8192, 16384, 8192, 8192, 8192, 16384, 16384, 16384, 16384}

    Returns: {688128, 0, 1 }

  26. {4009500, 3074048, 1341706, 2377580, 8639918, 2821088, 2775116, 1295770, 1555070, 2113092, 9883636, 6606616, 5843714, 2043378, 6956954, 4947180, 1073842}

    Returns: {67358208, 2, 1 }

  27. {384, 256, 1280, 4736, 7552, 55808, 60544, 246144, 14848, 17024, 1664, 128, 384, 81792, 384, 9088, 5504, 238208, 31872, 40576, 1408, 137984, 65024, 5248, 173952, 2304, 128, 128, 3456, 1408, 7040, 640, 17408, 3200, 9984, 14976, 8064, 2176, 129792, 1536, 9088, 128, 1792, 4736, 6784, 18560, 384, 2304, 640, 20480}

    Returns: {1468928, 0, 1 }

  28. {4978048, 99648, 1915776, 9469376, 199040, 4212864, 8949056, 3573568, 8930624, 6252416, 7902272, 3594688, 5577152, 6718720, 643200, 9839488, 6957888, 5460160, 9019456, 5783552, 125568, 1833600, 344896, 5217280, 815232, 3668800, 8795264, 56384, 585792, 9305600, 9867392, 826432, 6433216, 7785280, 3203968, 1506176, 2601600}

    Returns: {173049472, 1, 1 }

  29. {64, 192, 64, 192, 384, 256, 192, 128, 448, 128, 128, 64, 64, 64, 192, 192, 320, 64, 448, 128, 64, 320, 320, 64, 64, 320, 384, 448, 448, 256, 64, 64, 64, 448, 448, 192, 192, 320, 384}

    Returns: {8576, 0, 1 }

  30. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: {38, 0, 1 }

  31. {3480576, 4969888, 7483456, 5456032, 1916288, 2453792, 9932512, 3071488, 4369344, 5755392, 4596800, 1588352, 4941984, 3489696, 635296, 4539104, 3641664, 3327872, 8260256, 8308128, 1299264, 6404672, 390624, 9946016, 2514976, 1785568, 7034976, 5049920, 3696512, 6946560, 3184160, 1445472, 3593952, 3749888, 9194624, 1497824, 9320672, 7034400, 5185056, 5290944, 6273120, 1992224, 49920}

    Returns: {195099264, 1, 1 }

  32. {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

    Returns: {104, 0, 1 }

  33. {6, 4, 2, 4, 4, 2, 2, 2, 6, 2, 4, 2, 6, 2, 2, 4, 2, 4, 2, 6, 2, 6, 6, 2, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 4, 4, 2, 4, 4, 4, 2, 2, 6, 2}

    Returns: {144, 0, 1 }

  34. {32, 64, 64, 64, 64, 32, 32, 32}

    Returns: {384, 0, 1 }

  35. {1024, 1024, 512, 1024, 1536, 512, 1536, 1536, 512, 512, 1536, 512, 1024, 1536, 512, 1536, 1024, 1536, 512, 1024, 512, 1024, 1536, 1024, 1024, 512, 512, 1024, 1536, 1536, 512, 512}

    Returns: {31744, 2, 1 }

  36. {8860928, 5128192, 3096832, 6657024, 4717440, 9927680, 3382656, 8859264, 4702080, 2691840, 2708736, 5370496, 2570880, 4667904, 8088064, 1656192, 4793216, 4385664, 2533504, 6560640, 12241792}

    Returns: {113601024, 4, 1 }

  37. {1446784, 4866560, 8671104, 2445312, 7803648, 4952704, 529792, 1788288, 9309952, 3705728, 3478400, 1783552, 3304192, 8378496, 6430080, 5074048, 4284032, 204288, 5627392, 6046208, 6499712}

    Returns: {96630272, 0, 1 }

  38. {46, 1306, 30, 716, 8750, 5468, 2, 26, 22, 444, 28, 12602}

    Returns: {29440, 0, 1 }

  39. {596520, 6823256, 7820344, 3889496, 7105736, 305048, 7092768, 8600840, 1106296, 8231016, 3244152, 6557280, 3146040, 34552, 4019464, 8258472, 8720760, 196920, 9236320, 4959064, 8042288, 5272112, 5140544, 8708416, 8469888, 6300312, 3731720, 903808, 3649248, 3666016, 8241616, 9863536, 7399384, 8361512, 6709712, 9123344, 6746880, 2348000, 7022976, 5993232, 216840, 8794024, 5698560, 9156056, 11577328}

    Returns: {261081696, 0, 1 }

  40. {928840, 2672, 16, 24, 2768, 28624, 1296, 1240, 216, 16, 448, 2304, 5485896, 1680, 199928, 104, 2080, 13071400, 1609808, 253488, 216, 176, 8, 24, 370160, 689776, 14557904, 16, 1548464, 513512, 73008, 384976, 864712, 754984, 62656, 168, 352, 8216, 2935984, 1987736, 400, 979888, 16313296, 1963040, 8, 9987408}

    Returns: {75589936, 0, 1 }

  41. {9355264, 835584, 1024000, 1712128, 3489792, 8093696, 3162112, 9256960, 540672, 8953856, 2023424, 278528, 5570560, 4341760, 8052736, 4669440, 1654784, 1966080, 6021120, 8110080, 155648, 4677632, 9592832, 7725056, 7487488, 3121152, 2072576, 4341760, 6193152, 7823360, 909312, 7667712}

    Returns: {150880256, 2, 1 }

  42. {3523968, 6219370, 3291182, 3866592, 9820588, 2402624, 3455020, 8312572, 8624246, 1789568, 4875508, 9066252, 1668292, 8220992, 3257596, 634070, 2520124, 8492702, 4336700, 2485668, 4705968, 6258188, 2463986, 5581880, 8922516, 6212724, 2132076, 2405522, 7184826, 6823828, 9576368, 5328672, 3016684, 924088}

    Returns: {168400960, 1, 1 }

  43. {7122944, 2801664, 1093632, 1691648, 2179072, 1732608, 1286144, 6782976}

    Returns: {24690688, 0, 1 }

  44. {1, 125, 33, 1, 5, 40, 5, 2, 10, 8, 1, 59, 18, 109, 3, 5, 1, 54}

    Returns: {480, 0, 1 }

  45. {3, 2, 3, 1, 1, 2, 3, 2, 1}

    Returns: {18, 0, 1 }

  46. {5742592, 3506176, 4358144, 5742592, 2031616, 2555904, 9994240, 7561216, 6356992, 9756672, 5644288, 466944}

    Returns: {63717376, 0, 1 }

  47. {12, 12, 44, 4, 4, 4, 20, 60, 8, 4, 16, 24, 24, 8, 16, 60, 28, 12, 4, 48, 8, 4, 4, 20}

    Returns: {448, 0, 1 }

  48. {3563520, 950272, 4571136, 9732096, 9764864, 3571712, 8650752, 647168, 5398528, 4603904, 2236416, 6987776, 2015232, 1941504, 3833856, 8904704, 3014656, 3047424, 1867776, 6569984, 5439488, 4505600, 122880, 8396800, 8978432, 4587520, 2973696, 8560640, 147456, 8650752, 9871360, 5160960, 9633792, 4997120, 6881280, 9666560, 9797632, 4554752}

    Returns: {204800000, 0, 1 }

  49. {96, 416, 1440, 96, 512, 320, 864, 288, 32, 928, 2656, 1376, 2720, 288, 96, 1792, 96, 1152, 2016, 64, 32, 1536}

    Returns: {18816, 0, 1 }

  50. {2324736, 9329472, 6594048, 6169600, 3890880, 1825280, 4191872, 3348032, 6487616, 4323136, 9883264, 7733696, 6648064, 7062720, 8114944, 579008, 2781440, 2603456, 3251136, 5961984, 9995968, 8930048, 5886080, 2475008, 791296, 610432, 2137536, 3086336, 3012800, 845888, 2368640}

    Returns: {143244416, 1, 1 }

  51. {8493210, 2235938, 511144, 5762781, 4243543, 5065760, 6952374, 2402318, 7511441, 7443495, 2704805, 2682107, 8898584, 7153859, 220544, 2155602, 3045967, 8255637, 2125612, 557333}

    Returns: {88422054, 3, 1 }

  52. {9764384, 7697440, 3419616, 5078176, 2815744, 4683648, 8663712, 7432544}

    Returns: {49555264, 0, 1 }

  53. {3072, 10085888, 454656, 12126208, 1489920, 501760, 89600, 6144, 512, 35840, 17920, 70144, 1536, 23040, 16384, 23552, 5632, 3072, 7168, 4696576, 645632, 3584, 28160, 129024, 130048, 350720, 8998400, 62976, 28160, 43520, 190976, 119296, 2291712, 26112, 391168, 4065280, 5632, 1536, 919552, 375808, 68608, 24064, 6656, 1518080, 512, 1133568, 218624, 216576, 14886912}

    Returns: {66539520, 1, 1 }

  54. {1024, 1024, 1024, 3072, 1024, 3072, 3072, 2048, 2048, 1024, 2048, 3072, 3072, 1024, 3072, 3072, 1024, 3072, 2048, 3072, 1024, 2048, 1024, 1024, 3072, 2048, 1024, 1024, 1024, 2048, 1024, 1024, 1024, 1024, 1024, 2048, 1024, 1024}

    Returns: {67584, 0, 1 }

  55. {6630402, 9281882, 7876296, 6762080, 641178, 9052386, 2846608, 3276278, 9409716, 895434, 5711980, 1554086, 4540412, 8492404, 7754204, 7448334, 6821730, 485218}

    Returns: {99480628, 0, 1 }

  56. {128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128}

    Returns: {2560, 0, 1 }

  57. {3, 3, 1, 1, 1, 3, 3, 1}

    Returns: {16, 0, 1 }

  58. {2738542, 3493652, 8059332, 6228466, 5096852, 2642814, 6715184, 5365540, 9859222, 6425748, 1931354, 1981666, 7060036, 117934, 407226, 3350698, 6523852, 2864738, 8103220, 15763560}

    Returns: {104729636, 0, 1 }

  59. {3507524, 1310546, 7148569, 6898898, 3334903, 3710907, 9726275, 2306006, 7942696, 9407565, 7538960, 1299281, 2677833, 5201674, 1320123, 7257286, 9794008, 6737982, 4835154, 8770991, 2992233, 423276}

    Returns: {114142690, 2, 1 }

  60. {8, 4, 6, 14, 6, 18, 4, 6, 14, 28, 22, 10, 18, 2, 22, 6, 2, 2, 12, 24, 2, 16, 2, 2, 2, 2, 2, 14, 22}

    Returns: {292, 2, 1 }

  61. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: {38, 0, 1 }

  62. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: {42, 0, 1 }

  63. {6197248, 40960, 126976, 3932160, 4612096, 737280, 1929216, 7520256, 5582848, 7790592, 4014080, 7213056, 9519104, 131072, 4718592, 7454720, 6549504, 5459968, 2637824, 6090752, 5406720, 6250496, 5894144, 3932160, 5591040, 4341760, 6852608, 540672, 3215360, 4804608, 12111872}

    Returns: {151199744, 0, 1 }

  64. {6684672, 1441792, 4587520, 7995392, 1966080, 1048576, 917504, 2621440, 4849664, 3014656}

    Returns: {35127296, 0, 1 }

  65. {9568, 480, 106784, 2944, 384, 608, 224, 37344, 448, 7552, 46592, 768, 32, 28768, 672, 32, 213120, 64, 197440, 2720, 160, 5632, 448, 3136, 96, 960, 4576, 32, 32, 32, 15040, 175616, 6464, 6688, 3904, 4992, 199744}

    Returns: {1084096, 0, 1 }

  66. {4390912, 1015808, 65536, 9666560, 6717440, 983040, 8617984, 491520, 8454144, 1638400, 2326528, 622592, 9601024, 7798784, 4128768, 5373952, 7864320, 6127616, 7536640, 6258688, 1179648, 6979584, 7471104, 9109504, 4554752, 2097152, 5505024, 196608, 8257536, 9568256, 8716288, 8912896, 5308416, 9240576, 7864320, 1867776, 3178496, 7438336, 1179648, 4161536, 3375104, 11894784}

    Returns: {227737600, 1, 1 }

  67. {46848, 53248, 5376, 56832, 2048, 66560, 5376, 44800, 51712, 85504, 496384, 16128, 366080, 512, 19712, 3328, 266496, 456448}

    Returns: {2043392, 0, 1 }

  68. {796310, 7591534, 5649868, 8862676, 8355106, 6185562, 2195052, 2037174, 4007102, 2281650, 854402, 1255084, 11555168}

    Returns: {61626688, 0, 1 }

  69. {2214272, 4031264, 1916704, 6135200, 5439472, 6645680, 6906912, 6779712, 6755024, 3390896, 4079904, 6730112, 6931568, 4399616, 9511440, 2348064, 6913936, 2937232, 8169184, 3891584, 2918896, 7382720, 410352, 2321536, 353808, 597984, 870096, 3164192, 5257808, 2973488, 6014288, 6698800, 5722624, 3521680, 1883680, 7189248, 5792560, 2655056, 1493168, 5252336, 6386192, 1714032, 8489424, 3292304, 1754816, 813520}

    Returns: {201052384, 4, 1 }

  70. {174080, 442880, 836096, 14336, 512, 512, 41984, 9216, 30208, 128512, 217088, 3072, 1024, 3072, 14336, 600576, 5200896, 278016, 511488, 256000, 20992, 3584, 434176, 3584, 2955264, 4096, 92160, 154112, 3457024, 1024, 1024, 157184, 114688, 2647040, 442880, 1688064, 512, 64000, 2048, 322048, 12288, 6320640}

    Returns: {27662336, 1, 1 }

  71. {6356992, 1310720, 2097152, 917504, 9895936, 9109504, 1703936, 5242880, 1966080, 7536640, 6291456}

    Returns: {52428800, 0, 1 }

  72. {5120, 3072, 1024, 2048, 1024, 30720, 3072, 7168, 41984, 6144, 12288, 1024, 5120, 4096, 5120, 1024, 1024, 25600, 24576, 58368}

    Returns: {239616, 0, 1 }

  73. {3400680, 8878088, 7663704, 3953776, 3973664, 6482072, 7052264, 5997880, 5872816, 8856840, 4690576, 7536320, 4262872, 5179056, 4257816, 9652936, 2984952, 5017968, 3891624, 9080144, 9958448, 8688088, 761432, 4615984, 2543736, 9187872, 8577584, 5396184, 683192, 7492592, 1394720, 158728, 9447920, 1113504, 4852840, 4047776, 3462720, 3900032, 1906416, 1428408, 5644784, 3007904, 8598480, 8690736, 4604160, 2748432, 4484944, 7012832, 1439872, 15134800}

    Returns: {269671168, 0, 1 }

  74. {64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 4, 4, 4, 4, 64, 64, 22, 64, 64, 64, 64, 64, 64, 64, 22, 64 }

    Returns: {1340, 16, 1 }

  75. {3, 1, 2 }

    Returns: {6, 0, 1 }

  76. {6, 4, 11, 9 }

    Returns: {30, 2, 1 }

  77. {88, 14, 86 }

    Returns: {188, 1, 1 }

  78. {6, 5, 3 }

    Returns: {14, 1, 1 }

  79. {8, 8, 15, 7, 8 }

    Returns: {46, 2, 1 }

  80. {3, 5, 6 }

    Returns: {14, 0, 1 }

  81. {25704, 62192, 45020, 17804, 31944 }

    Returns: {182664, 2, 1 }

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: