Statistics

Problem Statement for "LongLongNim"

Problem Statement

LongLongNim is a game played by two players who alternate turns. n coins are arranged in a pack. A valid move consists of removing exactly X coins from the pack, where X is an element of the set moves. If a player cannot perform a valid move during his turn, he loses the game, and the other player, of course, wins.

You are given the set moves as a int[], and you are also given an int maxN. Return the number of different values of n between 1 and maxN, inclusive, that make the game possible to win for the second player (assuming both players play optimally).

Definition

Class:
LongLongNim
Method:
numberOfWins
Parameters:
int, int[]
Returns:
int
Method signature:
int numberOfWins(int maxN, int[] moves)
(be sure your method is public)

Constraints

  • maxN will be between 1 and 1000000000 (109), inclusive.
  • moves will contain between 1 and 22 elements, inclusive.
  • Each element of moves will be between 1 and 22, inclusive.
  • moves will be sorted in strictly increasing order (i.e., no duplicates).

Examples

  1. 20

    {1,2,3}

    Returns: 5

    If n is a multiple of 4, the second player can win by simply removing 4-L coins each time, where L is the number of coins the first player removed on his last turn. If n is not a multiple of four, the first player can always choose to remove the remainder of dividing n by 4, thereby leaving a multiple of 4 and the second player in. After that, he just uses the strategy described at the beginning to win. Altogether, the second player only wins if n is a multiple of 4, and there are 5 multiples of 4 between 1 and 20.

  2. 999

    {1}

    Returns: 499

    The second player wins when n is even and loses when n is odd.

  3. 1000000000

    {1,2}

    Returns: 333333333

    Similarly to example 0, the second player only wins when n is a multiple of 3.

  4. 6543

    {2,4,7,11,20}

    Returns: 1637

    Any player who is left with 0 or 1 coin loses because the least number of coins that can be removed is 2.

  5. 1

    {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}

    Returns: 1

  6. 1

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}

    Returns: 0

  7. 1

    {1}

    Returns: 0

  8. 1000000000

    {2,19}

    Returns: 476190477

  9. 1000000000

    {2,6,7,11,12,16,18}

    Returns: 203821657

  10. 999999999

    {2,6,7,11,12,16,17}

    Returns: 304347826

  11. 1000000000

    {22}

    Returns: 500000005

  12. 999999999

    {5,17,22}

    Returns: 270270270

  13. 20

    {21,22}

    Returns: 20

  14. 65

    {1,4,7,11,20}

    Returns: 16

  15. 64

    {1,4,7,11,20}

    Returns: 16

  16. 1000000000

    {2,3,7,8,12,13,17,18,22}

    Returns: 400000000

  17. 999999999

    {2,3,7,8,12,13,17,18}

    Returns: 399999999

  18. 999987678

    {2,6,7,11,12,16,17,21,22}

    Returns: 285710765

  19. 123456789

    {2,6,7,11,12,16,18}

    Returns: 25163168

  20. 987654321

    {3,7,8,12,13,17,19}

    Returns: 301783264

  21. 567567865

    {2,6,7,11,12,16,17,20,22}

    Returns: 162162246

  22. 1000000000

    {15,17,19,21,22}

    Returns: 405405406

  23. 999999997

    {4,20,21,22}

    Returns: 380952381

  24. 302981977

    {1,3,4,5,6,10,11,12,13,14,15,18,20,21}

    Returns: 37872747

  25. 785921192

    {1,4,5,8,10,13,20,21,22}

    Returns: 157184238

  26. 541431219

    {4,6,10,11,13,15,18,20}

    Returns: 90238539

  27. 66830053

    {2,8,9,12,19,20}

    Returns: 19094301

  28. 708147906

    {1,3,5,8,18,20}

    Returns: 202327974

  29. 486174754

    {3,4,5,6,10,17}

    Returns: 105690164

  30. 548216988

    {3,5,10,11,15,17}

    Returns: 137054246

  31. 258630462

    {1,2,4,8,11,17,19,21}

    Returns: 47642454

  32. 933193086

    {1,4,5,6,9,11,12,15,18,19,22}

    Returns: 186638616

  33. 609505906

    {3,5,6,7,9,10,11,13,17,19,20,21}

    Returns: 90297171

  34. 999999991

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}

    Returns: 43478260

  35. 741302990

    {19,22}

    Returns: 343530658

  36. 391207276

    {17,18,19,20,21}

    Returns: 175013788

  37. 721172640

    {18,19,20,22}

    Returns: 324527688

  38. 954337139

    {18,20,21,22}

    Returns: 429451721

  39. 293872405

    {17,19,21,22}

    Returns: 128098229

  40. 162493626

    {2,3,4,5}

    Returns: 46426751

  41. 660103999

    {3,5}

    Returns: 247538999

  42. 449723762

    {2,4,5}

    Returns: 128492503

  43. 874999758

    {2,3,5}

    Returns: 249999931

  44. 505767449

    {2,3,4}

    Returns: 168589149

  45. 19

    {3,4,6,20,22}

    Returns: 7

  46. 22

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}

    Returns: 0

  47. 22

    {22}

    Returns: 21

  48. 21

    {22}

    Returns: 21

  49. 545718776

    {13,22}

    Returns: 202695546

  50. 353285238

    {9,14,21}

    Returns: 105985574

  51. 643572703

    {8}

    Returns: 321786351

  52. 372777587

    {4,10,12,20,21,22}

    Returns: 93194399

  53. 377513176

    {1,5,8,12,14,20}

    Returns: 107860907

  54. 48873580

    {9,11,19,21}

    Returns: 14662079

  55. 126967094

    {1,2,3,4,8,9,12,13,14,15,17,20,21,22}

    Returns: 14937306

  56. 212690885

    {3,5,7,8,10,11,13,14,15,17,18,19,21,22}

    Returns: 25522907

  57. 862343671

    {1,2,3,4,5,6,7,8,9,10,11,13,14,15,17,18,19,20,22}

    Returns: 71861972

  58. 478763709

    {2,3,4,6,8,9,14,15,19,20,21}

    Returns: 83263253

  59. 102654020

    {1,2,3,4,6,9,11,12,15,18,19,21}

    Returns: 11406002

  60. 724924749

    {1,3,4,5,7,8,10,11,12,13,14,15,17,18,19}

    Returns: 65902249

  61. 945170309

    {4,11,12,13,15,17,21,22}

    Returns: 203262432

  62. 971154114

    {20}

    Returns: 485577059

  63. 596655160

    {2,3,6,7,9,11,12,14,16,17,19}

    Returns: 74581895

  64. 228157164

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}

    Returns: 9919876

  65. 935018348

    {3,4,7,9,11,12,13,14,17,19,20,21}

    Returns: 116877293

  66. 906046245

    {5,7,8,9,12,16,17,19,21}

    Returns: 174239664

  67. 5865438

    {6,7,8,11,13,16,17,19,20}

    Returns: 1353563

  68. 138759937

    {5,6,9,16,19,22}

    Returns: 36515773

  69. 50243106

    {8,16,17}

    Returns: 16077798

  70. 214571048

    {7,8,10,13,14,19,20,21}

    Returns: 53642763

  71. 483159105

    {2,3,4,9,12,15,17}

    Returns: 90592333

  72. 687303295

    {3,7,8,9,10,12,14,21}

    Returns: 137460659

  73. 888223341

    {9}

    Returns: 444111672

  74. 328234641

    {3,4,7,8,13,18}

    Returns: 89518538

  75. 943932181

    {8,10}

    Returns: 419525415

  76. 38069871

    {2}

    Returns: 19034935

  77. 830624996

    {19}

    Returns: 415312506

  78. 899714635

    {1,5,10}

    Returns: 299904879

  79. 31740164

    {1,12,21}

    Returns: 14427346

  80. 132755278

    {2,6,7,19}

    Returns: 51059723

  81. 823006836

    {6,7,18}

    Returns: 362123008

  82. 190468360

    {4,9,12}

    Returns: 81629296

  83. 245658853

    {6,16}

    Returns: 111663115

  84. 677867035

    {8,15}

    Returns: 235779839

  85. 999999908

    {4, 9, 11, 18, 20, 21 }

    Returns: 217777760

  86. 1000000000

    {2, 5, 7, 11, 21 }

    Returns: 230769231

  87. 998457158

    {2, 3, 4, 12, 13, 14, 17, 21 }

    Returns: 199691433

  88. 999999999

    {3, 8 }

    Returns: 454545454

  89. 1000000000

    {2, 7, 10, 12, 15, 20, 22 }

    Returns: 174418604

  90. 543671

    {4, 11, 13, 21 }

    Returns: 203876

  91. 1000000000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22 }

    Returns: 43478260

  92. 15

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22 }

    Returns: 0

  93. 724867124

    {1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 15, 16, 17, 18, 19, 20, 21, 22 }

    Returns: 51776223

  94. 100000

    {3, 6, 10 }

    Returns: 30769

  95. 1000000000

    {2, 4, 7, 11, 20, 22 }

    Returns: 333333330

  96. 9699690

    {2, 3, 5, 7, 11, 13, 17, 19, 21, 22 }

    Returns: 1616615

  97. 1000000000

    {1, 4 }

    Returns: 400000000

  98. 1000000000

    {9, 11, 16 }

    Returns: 360000000

  99. 200000000

    {17, 18, 19, 20, 21, 22 }

    Returns: 87179490

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: