Statistics

Problem Statement for "DivNim"

Problem Statement

DivNim is a version of the NIM game.

This version is played with a whiteboard. At any moment during the game there is a collection of (not necessarily distinct) positive integers written on the board. Two players take alternating turns. In each turn, the current player chooses one number (let's call it X), erases it and in its place writes a proper divisor of X. The game ends when there are no more moves left.

For example, if the board has the numbers { 1, 12, 27, 12 }, the current player can either erase one of the 12s and then write 1, 2, 3, 4, or 6 instead of it, or they can erase the 27 and replace it with 1, 3, or 9.


DivNim can be played in two ways: in normal play the player who's unable to make a move loses, and in misere play that player wins the game.


You are going to play a game of DivNim against Shawn, the local DivNim champion who always plays optimally. You already made the agreement that all starting numbers will be between lo and hi, inclusive. Some such numbers are already on the whiteboard; these are given in the long[] board.

Before the game starts you have to add exactly one additional number N to the whiteboard. (The number you add must be within the allowed range. It can be a duplicate of a number already on the board.) Then, Shawn will be the one to take the first turn of the game.


For each mode of play, count the number of ways in which you can choose N so that you can win the game (if you play optimally). Return a int[] with two elements: the answer for normal play, followed by the answer for misere play.

Definition

Class:
DivNim
Method:
solve
Parameters:
long, long, long[]
Returns:
int[]
Method signature:
int[] solve(long lo, long hi, long[] board)
(be sure your method is public)

Constraints

  • lo will be between 1 and 10^12, inclusive.
  • hi will be between lo and 10^12, inclusive.
  • hi - lo will not exceed 10^5.
  • board will contain between 0 and 50 elements, inclusive.
  • Each element of board will be between lo and hi, inclusive.

Examples

  1. 1

    12

    {}

    Returns: {1, 5 }

    The board is empty, so you will be playing only with the number N you'll add to the board. If you are playing with the normal rule, you can only win if you choose N = 1 (in which case Shawn immediately has no valid move and loses). In all other scenarios Shawn erases your N, writes down 1 instead, and then you lose. If you are playing with the misere rule, you should choose one of the available primes (2, 3, 5, 7, or 11) as your N. If you choose N = 1, Shawn wins immediately, and in all other scenarios Shawn can make sure that he wins after your first move.

  2. 12

    12

    {12, 12, 12, 12, 12}

    Returns: {1, 1 }

    You must add a sixth 12 to the board. This creates a symmetric position, and in both modes of play you can use that symmetry to your advantage and defeat Shawn.

  3. 10

    30

    {12, 16, 29, 24, 28}

    Returns: {6, 6 }

  4. 1

    12

    {1, 1, 1}

    Returns: {1, 5 }

    As you cannot do anything with a 1 written on the whiteboard, this example is essentially the same as Example #0.

  5. 1

    30

    {4, 8}

    Returns: {10, 10 }

    xor = 1 but items aren't small only

  6. 1

    30

    {4, 7, 8}

    Returns: {1, 1 }

    xor = 0 but items aren't small only

  7. 999999900000

    1000000000000

    {}

    Returns: {0, 3613 }

  8. 999999900000

    1000000000000

    {999999927430, 999999972431, 999999973387, 999999905368, 999999957622, 999999922756, 999999979950, 999999920309, 999999965744, 999999927696, 999999992391, 999999907288, 999999906323, 999999929274, 999999945339, 999999976826, 999999935878, 999999922679, 999999949401, 999999936664, 999999968465, 999999954643, 999999968946, 999999911479, 999999914597, 999999944528, 999999993931, 999999980476, 999999993596, 999999960504, 999999931505, 999999914630, 999999989601, 999999943816, 999999980729, 999999974672, 999999916367, 999999901611, 999999923882, 999999916821, 999999991601, 999999940070, 999999974044, 999999986361, 999999974769, 999999994508, 999999901946, 999999910804, 999999924720, 999999900665}

    Returns: {0, 0 }

  9. 999999900000

    1000000000000

    {999999972431, 999999973387, 999999905368, 999999957622, 999999922756, 999999979950, 999999920309, 999999965744, 999999927696, 999999992391, 999999907288, 999999906323, 999999929274, 999999945339, 999999976826, 999999935878, 999999922679, 999999949401, 999999936664, 999999968465, 999999954643, 999999968946, 999999911479, 999999914597, 999999944528, 999999993931, 999999980476, 999999993596, 999999960504, 999999931505, 999999914630, 999999989601, 999999943816, 999999980729, 999999974672, 999999916367, 999999901611, 999999923882, 999999916821, 999999991601, 999999940070, 999999974044, 999999986361, 999999974769, 999999994508, 999999901946, 999999910804, 999999924720, 999999900665}

    Returns: {16820, 16820 }

  10. 1

    64327

    {46972, 45063, 23164}

    Returns: {11882, 11882 }

  11. 1

    46

    {33, 40, 35, 31, 28, 24, 3, 39, 17, 42, 39, 34}

    Returns: {10, 10 }

  12. 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: {1, 0 }

  13. 1

    1

    {1, 1, 1}

    Returns: {1, 0 }

  14. 1

    51

    {40, 48, 28, 24, 4, 23, 38, 4, 26, 41, 18, 17, 14, 19, 14, 30, 43, 20, 29, 50, 29, 21, 44, 4, 10, 38, 31, 1, 2, 28, 30, 34, 29, 40, 17, 19, 7}

    Returns: {18, 18 }

  15. 1

    945

    {628, 186}

    Returns: {1, 1 }

  16. 1

    15756

    {}

    Returns: {1, 1837 }

  17. 1

    29

    {23, 16, 11, 21, 21, 4, 9, 16, 26, 3}

    Returns: {6, 6 }

  18. 1

    620

    {528, 173, 170, 80, 95, 129, 604, 404, 357, 125, 425, 302, 563, 225, 356, 93, 322, 105, 37, 207}

    Returns: {21, 21 }

  19. 1

    3385

    {415, 1799, 3168, 2388, 509, 395, 1371}

    Returns: {0, 0 }

  20. 74929704

    75029365

    {74935499, 75013843, 75010625, 75017433, 74930530, 74963282}

    Returns: {0, 0 }

  21. 2803405

    2903401

    {2838375, 2811840, 2824672, 2830238, 2833214, 2858730, 2865355, 2829285, 2842295, 2804183, 2818371, 2882639, 2877384, 2804959, 2836317}

    Returns: {4077, 4077 }

  22. 14485407639

    14485507638

    {14485457898, 14485468461}

    Returns: {5758, 5758 }

  23. 17367

    117365

    {78107, 70682, 112855, 111782, 60963, 111671, 29154}

    Returns: {25473, 25473 }

  24. 4918268

    5018267

    {}

    Returns: {0, 6519 }

  25. 124405340

    124504892

    {124482653, 124436990, 124501152, 124482380, 124422152, 124414581, 124407637, 124423293}

    Returns: {39, 39 }

  26. 437850905978

    437851005317

    {437850924543, 437850967236, 437850957408}

    Returns: {3347, 3347 }

  27. 116109818966

    116109918966

    {116109868823, 116109917809, 116109841502}

    Returns: {21425, 21425 }

  28. 1439326353

    1439426313

    {1439406723, 1439411633, 1439354803}

    Returns: {4779, 4779 }

  29. 1239946637

    1240046579

    {1240030827, 1240029777, 1240033735, 1239975932, 1240018469, 1239958338, 1240019454, 1240001593, 1239987145, 1239987972, 1239995645, 1239962201, 1239958574, 1240037355, 1239987828, 1240006223, 1239974405, 1239962033, 1240032264, 1239957993, 1240016867, 1240033710}

    Returns: {15497, 15497 }

  30. 1964137

    2064125

    {2015370, 2024982, 2055166, 2023126, 2002707, 2045610, 1976450, 2047947}

    Returns: {24637, 24637 }

  31. 1540557

    1640545

    {1631044, 1615876}

    Returns: {3870, 3870 }

  32. 563242937

    563342917

    {563274989, 563333241}

    Returns: {15297, 15297 }

  33. 650874

    750844

    {675580}

    Returns: {12800, 12800 }

  34. 90400299

    90500299

    {90491278, 90434561, 90420091, 90451553, 90488701, 90429049, 90429371, 90499004, 90423644, 90411601, 90438318, 90468041, 90419402, 90461264, 90438991, 90404437, 90414269, 90489387, 90473032, 90429249, 90427473, 90414232, 90426112, 90465755, 90450533, 90439939, 90494225, 90433767, 90401894, 90444262, 90447534, 90455345, 90412972, 90411825, 90443498, 90434385, 90470201, 90430673, 90476455, 90494589, 90490750, 90418352, 90432535, 90488567, 90465477, 90472501, 90491795, 90483154, 90426597, 90404770}

    Returns: {8701, 8701 }

  35. 48592050635

    48592150400

    {48592057555, 48592124434, 48592084940, 48592140853, 48592084523}

    Returns: {21375, 21375 }

  36. 401036491571

    401036591531

    {401036498668}

    Returns: {16722, 16722 }

  37. 16574786

    16674781

    {16665678, 16666911, 16665054, 16605494, 16641970, 16650288, 16617339}

    Returns: {52, 52 }

  38. 3092320046

    3092419875

    {3092367074, 3092383393, 3092321232, 3092356543, 3092394946, 3092380354, 3092378505, 3092344377, 3092336203, 3092353957, 3092368367, 3092381105, 3092327111, 3092384533, 3092410782, 3092324341, 3092375864, 3092404132, 3092330782, 3092410348, 3092419693, 3092411682, 3092347576, 3092368634, 3092345758, 3092350253, 3092414947, 3092396769, 3092338816, 3092347038, 3092384987, 3092387422, 3092417655, 3092334026, 3092358135, 3092399465, 3092403638, 3092416917, 3092409881}

    Returns: {2830, 2830 }

  39. 16496515788

    16496615400

    {16496566475}

    Returns: {21687, 21687 }

  40. 34352066712

    34352166626

    {34352087521, 34352121649, 34352139294, 34352070538, 34352076230, 34352098705, 34352155411}

    Returns: {13968, 13968 }

  41. 2419284700

    2419384697

    {2419292453, 2419353310}

    Returns: {9627, 9627 }

  42. 323504

    423498

    {404943, 368318, 350860, 357543, 368332, 414365, 339325, 405096, 343426, 401568, 382569, 373129, 399705, 367539, 350009, 357291, 359464, 411634}

    Returns: {392, 392 }

  43. 402535249

    402635150

    {402620024, 402590230, 402600087}

    Returns: {0, 0 }

  44. 2312401587

    2312501353

    {}

    Returns: {0, 4598 }

  45. 2184110093

    2184210075

    {2184158124, 2184198527, 2184160275, 2184135331, 2184175322, 2184201873, 2184119331, 2184192404, 2184183171, 2184175173, 2184136112}

    Returns: {2824, 2824 }

  46. 628598

    728370

    {654754, 679282, 662372, 705810, 689017, 724312, 680535, 683775, 691995, 633121, 650327, 648937, 653997, 675175, 706691, 723313, 698363, 674582, 647933, 719481, 634779, 713252, 633366, 645297, 711662, 652709, 652135, 635206, 630156, 720302, 675429, 656237, 631646, 694951, 646066, 632591, 724405, 673619, 726445, 661750, 668174, 682913, 725997, 647366, 687281, 723461, 686750}

    Returns: {20368, 20368 }

  47. 6126255345

    6126355171

    {6126331629}

    Returns: {21517, 21517 }

  48. 377762337

    377862282

    {377814114}

    Returns: {9135, 9135 }

  49. 37078489446

    37078589398

    {37078506380, 37078569400, 37078556066, 37078570726}

    Returns: {39, 39 }

  50. 55356963

    55456962

    {55449812}

    Returns: {21005, 21005 }

  51. 28099481648

    28099581636

    {28099529408, 28099553197, 28099580624}

    Returns: {191, 191 }

  52. 416615313316

    416615412604

    {416615394716, 416615387338, 416615350860, 416615339727, 416615357830, 416615326546, 416615384019, 416615341556, 416615376600, 416615337394, 416615322442, 416615377841, 416615319888, 416615339857, 416615321528, 416615360687, 416615317936, 416615371088, 416615322100, 416615407903, 416615404380, 416615386782}

    Returns: {898, 898 }

  53. 32429808

    32529807

    {32433054, 32526061}

    Returns: {0, 0 }

  54. 2070258243

    2070357322

    {2070309210}

    Returns: {21145, 21145 }

  55. 122200054

    122300044

    {122270378, 122231998, 122201935, 122271159, 122218851, 122239591, 122266358, 122262851, 122200422, 122210852, 122265692, 122278527, 122271415, 122281229, 122275235, 122234855, 122262243, 122224434, 122228280, 122228685, 122243711, 122291269, 122211146, 122288041, 122278127, 122276457, 122265342, 122214566, 122202715, 122261186, 122289685, 122258359, 122203719, 122205566, 122265522, 122260275, 122227189, 122298353, 122215415}

    Returns: {33, 33 }

  56. 113392220718

    113392320336

    {113392252474, 113392224946, 113392258899}

    Returns: {3874, 3874 }

  57. 999991

    1099294

    {1050660, 1070626, 1057764, 1042566}

    Returns: {20072, 20072 }

  58. 63567

    163561

    {101083, 160272}

    Returns: {164, 164 }

  59. 654787625

    654887621

    {654867378, 654837222, 654824595}

    Returns: {4909, 4909 }

  60. 54465407

    54565397

    {54492008, 54465940, 54522580, 54467828}

    Returns: {5617, 5617 }

  61. 211878188

    211978184

    {211936380, 211949151, 211913531, 211894354, 211970143, 211921123, 211879691, 211942578, 211952931, 211946238, 211947811, 211967613, 211919637, 211950126}

    Returns: {5194, 5194 }

  62. 328038172

    328138137

    {328071302, 328119209, 328055264, 328055470, 328069666, 328053146, 328086103, 328080667, 328090091, 328092132, 328117030}

    Returns: {15993, 15993 }

  63. 30187375

    30287257

    {30237267, 30200765, 30280429, 30286813, 30253698, 30283198, 30213096, 30201084, 30285349, 30227737, 30259152, 30223137, 30257830, 30208920, 30268336, 30232614, 30271650, 30226394, 30222507, 30277638, 30236770, 30188066, 30223763, 30189125, 30266499, 30226670}

    Returns: {55, 55 }

  64. 43276543

    43376327

    {43300452, 43373852, 43367805, 43373860, 43321257, 43314870, 43327930, 43359862, 43286118, 43372800, 43364592, 43357869, 43292272, 43354992, 43372297, 43280568, 43354971, 43338892, 43345333, 43339202, 43324814, 43348040, 43296708, 43298846, 43327818, 43350894, 43372593, 43372623, 43355278, 43319599, 43300811, 43329281, 43346477, 43303365, 43308855, 43276906, 43335780, 43303401, 43349973}

    Returns: {290, 290 }

  65. 2581046148

    2581146141

    {2581086775, 2581061087, 2581104523, 2581108874}

    Returns: {5426, 5426 }

  66. 114356582230

    114356681365

    {114356602812, 114356583959, 114356592708, 114356617022}

    Returns: {0, 0 }

  67. 49239014785

    49239114779

    {49239045357}

    Returns: {16220, 16220 }

  68. 3456339651

    3456439231

    {3456342944, 3456365874, 3456412116, 3456419497, 3456363311, 3456406284, 3456403656, 3456386653, 3456413341, 3456385942, 3456382120, 3456396452, 3456339889, 3456373254, 3456347695, 3456384133, 3456419384, 3456343988, 3456344969, 3456353165, 3456393546, 3456379376, 3456405179, 3456393187, 3456391462, 3456390410, 3456373023, 3456428174, 3456412046, 3456435681, 3456376645, 3456421081, 3456359914, 3456378221, 3456369538, 3456371173}

    Returns: {0, 0 }

  69. 258130636

    258230633

    {258227421, 258208445, 258181123, 258204093, 258192442, 258192872, 258196534, 258201913, 258164069, 258179808, 258189528, 258176955, 258217221, 258202665, 258203014, 258140250, 258212707, 258178801, 258182899}

    Returns: {4962, 4962 }

  70. 1

    64327

    {51683, 7219, 25919}

    Returns: {6441, 1 }

  71. 1

    47247

    {28549, 44179, 11579, 33533, 13183, 37181, 24821, 15671, 40151, 36473, 7673, 46187}

    Returns: {1, 4871 }

  72. 1

    51

    {23, 41, 17, 19, 43, 29, 29, 31, 2, 29, 17, 19, 7, 11, 37, 17, 2, 3, 5, 5, 41, 47, 7, 7, 43, 31, 29, 13, 5, 7, 17, 23, 2, 17, 19, 47, 31}

    Returns: {15, 1 }

  73. 1

    620

    {173, 563, 37, 139, 587, 503, 439, 61, 419, 487, 7, 263, 353, 197, 569, 379, 137, 307, 433, 263}

    Returns: {1, 114 }

  74. 1

    12625

    {6011}

    Returns: {1508, 1 }

  75. 1

    15

    {13}

    Returns: {6, 1 }

  76. 1

    2415

    {1667, 1723}

    Returns: {1, 358 }

  77. 1

    1629

    {457}

    Returns: {258, 1 }

  78. 1

    16

    {5, 3, 5, 5, 5, 5, 11, 13}

    Returns: {1, 6 }

  79. 1

    38

    {}

    Returns: {1, 12 }

  80. 65729348

    65828908

    {65800061, 65763277, 65807633}

    Returns: {5531, 0 }

  81. 10150814

    10250702

    {10215347, 10215721, 10178891}

    Returns: {6119, 0 }

  82. 34326863752

    34326963726

    {34326947947, 34326943457, 34326943583, 34326922741, 34326887657, 34326866983, 34326946373, 34326901027, 34326923291, 34326923017, 34326884531, 34326922459}

    Returns: {0, 4058 }

  83. 650874

    750844

    {742507}

    Returns: {7412, 0 }

  84. 1478863376

    1478962927

    {1478924341, 1478881429, 1478924141, 1478897003, 1478870473, 1478946251, 1478911573, 1478887199, 1478863621, 1478919503, 1478935663, 1478933321, 1478867671, 1478928317, 1478959877, 1478876587, 1478914211, 1478887369, 1478906711, 1478887651, 1478870741, 1478867899, 1478909953, 1478927873, 1478866661, 1478949487, 1478875423, 1478905403, 1478930339, 1478867959, 1478880071, 1478921053, 1478897417, 1478934097, 1478898847, 1478956307, 1478875001, 1478903897, 1478960761, 1478868683, 1478892367, 1478873689, 1478922761, 1478892007, 1478939779, 1478892487, 1478959609, 1478867801, 1478937641, 1478915089}

    Returns: {0, 4748 }

  85. 3072403

    3171487

    {3166333, 3120919, 3093743, 3162847}

    Returns: {0, 6656 }

  86. 199844

    299723

    {207079, 250361}

    Returns: {0, 8004 }

  87. 2510439261

    2510538757

    {2510461609, 2510531239, 2510500021}

    Returns: {4592, 0 }

  88. 1205020047

    1205120046

    {}

    Returns: {0, 4818 }

  89. 69488541

    69588483

    {69560479, 69512843, 69556789, 69505633}

    Returns: {0, 5588 }

  90. 839760

    939642

    {865481, 884999, 840451, 858943, 851863, 898717, 928799, 918209, 869849, 912533, 932317, 907999, 937949, 923123, 924191, 881917, 913571, 894547, 896561, 891571, 842089, 913217, 901441, 853217, 912349, 842701}

    Returns: {0, 7291 }

  91. 1905900

    2005899

    {1910071, 1922867, 1981607, 2005723, 1916543, 1916737}

    Returns: {0, 6915 }

  92. 2088908

    2188908

    {}

    Returns: {0, 6861 }

  93. 513185448903

    513185548887

    {513185538953, 513185495321, 513185474959, 513185515309, 513185545619, 513185504801}

    Returns: {0, 3652 }

  94. 233403276

    233503227

    {233499061}

    Returns: {5176, 0 }

  95. 5456295248

    5456395243

    {5456366683}

    Returns: {4431, 0 }

  96. 2879173935

    2879273812

    {2879236303, 2879251589, 2879227531, 2879221831, 2879253803}

    Returns: {4584, 0 }

  97. 3578920

    3678908

    {3587891, 3592657, 3637577, 3659479}

    Returns: {0, 6668 }

  98. 110615898

    110715885

    {110677823, 110620919, 110648987, 110630321, 110709601}

    Returns: {5396, 0 }

  99. 112755252

    112855024

    {112818187, 112764251, 112782221, 112829609, 112817371, 112777963, 112774279, 112781237, 112803179, 112852591}

    Returns: {0, 5393 }

  100. 1

    64327

    {1, 1, 51683}

    Returns: {6441, 1 }

  101. 1

    46

    {1, 1, 1, 17, 1, 1, 37, 23, 1, 31, 7, 37}

    Returns: {1, 14 }

  102. 1

    49

    {17, 13, 1, 1, 5, 41, 2, 47, 37, 37, 1, 1, 23}

    Returns: {15, 1 }

  103. 1

    51

    {1, 1, 23, 41, 1, 1, 19, 43, 1, 1, 1, 1, 31, 2, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 37, 1, 1, 3, 5, 1, 1, 5, 1, 41, 1, 7, 7}

    Returns: {1, 15 }

  104. 1

    10

    {3, 2, 7, 1, 7, 1, 2, 1, 3, 1, 7, 1, 1, 1, 1, 1, 1, 7, 2, 7}

    Returns: {1, 4 }

  105. 1

    11445

    {7331, 4909, 1, 9257, 1, 6011}

    Returns: {1, 1380 }

  106. 1

    15

    {7}

    Returns: {6, 1 }

  107. 1

    24

    {1, 1}

    Returns: {1, 9 }

  108. 1

    56

    {47}

    Returns: {16, 1 }

  109. 1

    167

    {151, 19, 157, 1, 1, 1, 43, 31}

    Returns: {39, 1 }

  110. 999999899999

    999999999999

    {999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019, 999999900019 }

    Returns: {0, 3613 }

  111. 999999900005

    1000000000000

    {999999999999, 999999999987 }

    Returns: {110, 110 }

  112. 1

    2

    {2 }

    Returns: {1, 1 }

  113. 999999900000

    1000000000000

    {999999995904, 1000000000000, 999999963136, 999999959040, 999999930368, 999999974400, 999999991052, 999999952896, 999999977245, 1000000000000, 999999902433, 999999934229, 999999921093, 999999976814, 999999980264, 999999914375, 999999920373, 999999901085, 999999909649, 999999952856, 999999920433, 999999944878, 999999912885, 999999917178, 999999989068, 999999978825, 999999950466, 999999988630, 999999925256, 999999943766, 999999901322, 999999979967, 999999955831, 999999997049, 999999906571, 999999934168, 999999911298, 999999984304, 999999991197, 999999908513, 999999935109, 999999968388, 999999917009, 999999972261, 999999990986, 999999978868, 999999990030, 999999948530, 999999920641, 999999937299 }

    Returns: {931, 931 }

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: