Statistics

Problem Statement for "LastStone"

Problem Statement

Bob and Sally play the following game. At the beginning of the game several stones lie in a box. The two players take stones in turns, and the player who takes the last stone wins. On each turn, a player may take T stones for any T in turns. For each number k between m and n, inclusive, the game is played once with the box containing k stones at the start of the game. Assuming both players play optimally, return how many times Bob will win (Bob always moves first).

Definition

Class:
LastStone
Method:
numWins
Parameters:
int[], int, int
Returns:
int
Method signature:
int numWins(int[] turns, int m, int n)
(be sure your method is public)

Constraints

  • turns will contain between 1 and 50 elements, inclusive.
  • Each element of turns will be between 1 and 100, inclusive.
  • Elements of turns will be in strictly ascending order.
  • The first element of turns will be 1.
  • n will be between 1 and 100000, inclusive.
  • m will be between 1 and n, inclusive.

Examples

  1. {1, 3, 4}

    1

    5

    Returns: 4

    If the box contains 1, 3 or 4 stones, Bob wins by taking them all on his first turn. If the box contains 2 stones, Bob is forced to take 1 stone, and Sally wins by taking the other one. If the box contains 5 stones, Bob takes 3 stones (leaving 2 stones in the box) and wins the game on his next turn.

  2. {1}

    1

    100

    Returns: 50

  3. {1,2,3,4,5,6,7,8,9,10}

    1

    10

    Returns: 10

  4. {1, 2, 3}

    1

    8

    Returns: 6

  5. {1,2,4,8,16}

    1

    20

    Returns: 14

  6. {1, 6, 11, 16, 17, 18, 21, 29, 30, 32, 33, 35, 43, 46, 54, 60, 61, 65, 67, 69, 70, 77, 82, 83, 86, 92, 93}

    16224

    71736

    Returns: 50215

  7. {1, 13, 17, 19, 22, 28, 29, 38, 40, 41, 45, 46, 54, 56, 57, 63, 67, 74, 75, 76, 77, 79, 81, 82, 83, 85, 97, 100}

    21872

    29612

    Returns: 7026

  8. {1, 7, 8, 9, 22, 28, 29, 30, 34, 39, 42, 43, 44, 45, 46, 47, 51, 52, 58, 59, 67, 81, 86, 87, 88, 89, 92, 95, 96}

    50603

    82865

    Returns: 29755

  9. {1, 7, 9, 10, 12, 15, 20, 22, 33, 42, 47, 50, 54, 56, 61, 66, 69, 71, 72, 75, 81, 82, 83, 87, 90, 91, 93, 95, 96, 100}

    60

    4752

    Returns: 4259

  10. {1, 2, 8, 14, 15, 22, 24, 26, 27, 28, 33, 37, 38, 39, 42, 46, 50, 52, 62, 63, 68, 72, 73, 75, 77, 86, 88, 92, 94, 95, 97}

    24595

    62127

    Returns: 33243

  11. {1, 10, 17, 18, 19, 22, 28, 33, 35, 36, 45, 50, 51, 54, 55, 56, 58, 59, 62, 63, 64, 70, 71, 72, 73, 82, 86, 92, 93, 95, 96, 100}

    30269

    62357

    Returns: 28498

  12. {1, 19, 22, 24, 26, 27, 32, 33, 34, 36, 42, 45, 46, 48, 51, 55, 57, 60, 63, 64, 67, 68, 70, 73, 78, 79, 83, 84, 87, 93, 97, 99, 100}

    18833

    84365

    Returns: 59571

  13. {1, 4, 9, 10, 15, 16, 23, 24, 26, 28, 31, 32, 33, 36, 38, 39, 43, 46, 47, 52, 57, 61, 64, 65, 67, 73, 74, 75, 92, 94, 95, 96, 97, 100}

    10946

    44476

    Returns: 30822

  14. {1, 8, 9, 10, 14, 21, 26, 29, 32, 34, 35, 36, 37, 38, 42, 49, 50, 51, 53, 58, 60, 67, 68, 69, 73, 74, 76, 80, 83, 85, 86, 87, 92, 93, 97}

    59557

    92734

    Returns: 30625

  15. {1, 3, 4, 8, 9, 10, 13, 16, 20, 24, 25, 35, 37, 42, 44, 49, 51, 52, 53, 54, 56, 57, 64, 65, 67, 70, 77, 78, 81, 82, 84, 85, 86, 87, 92, 94}

    8648

    62216

    Returns: 49726

  16. {1, 10, 12, 21, 22, 24, 25, 28, 31, 34, 36, 37, 38, 39, 41, 45, 47, 49, 53, 59, 62, 64, 65, 69, 73, 74, 76, 77, 80, 82, 83, 87, 88, 90, 91, 95, 96}

    41981

    56346

    Returns: 13126

  17. {1, 6, 8, 13, 14, 19, 20, 22, 24, 27, 29, 30, 32, 35, 37, 39, 40, 42, 43, 45, 50, 56, 58, 59, 64, 65, 67, 68, 69, 70, 75, 78, 83, 84, 85, 90, 99, 100}

    68587

    89353

    Returns: 19254

  18. {1, 11, 12, 14, 20, 22, 23, 30, 31, 35, 36, 41, 42, 43, 47, 52, 54, 55, 56, 60, 62, 63, 64, 66, 67, 68, 72, 73, 75, 79, 83, 84, 88, 89, 91, 92, 94, 96, 97}

    57859

    80648

    Returns: 21524

  19. {1, 11, 15, 16, 19, 20, 24, 25, 28, 29, 30, 32, 33, 34, 35, 38, 40, 42, 46, 50, 53, 54, 55, 62, 63, 70, 71, 72, 73, 74, 76, 77, 79, 80, 88, 90, 92, 96, 99, 100}

    7126

    16369

    Returns: 8500

  20. {1, 2, 4, 5, 8, 9, 12, 14, 21, 24, 26, 27, 30, 32, 38, 39, 41, 42, 43, 45, 46, 50, 51, 60, 61, 63, 64, 67, 70, 71, 79, 80, 81, 82, 83, 86, 89, 91, 92, 95, 97}

    69107

    89592

    Returns: 18832

  21. {1, 7, 10, 20, 21, 23, 24, 26, 27, 28, 29, 31, 32, 34, 36, 37, 38, 40, 41, 46, 47, 48, 56, 57, 58, 59, 62, 65, 67, 68, 71, 75, 77, 80, 83, 84, 87, 88, 90, 92, 95, 98}

    33408

    36180

    Returns: 2573

  22. {1, 2, 3, 6, 9, 10, 12, 14, 17, 18, 21, 26, 31, 35, 37, 41, 42, 43, 45, 46, 47, 50, 51, 52, 53, 54, 55, 56, 58, 61, 65, 68, 73, 78, 79, 82, 87, 90, 91, 92, 96, 99, 100}

    7902

    67008

    Returns: 55584

  23. {1, 3, 4, 12, 14, 18, 19, 22, 23, 25, 26, 28, 30, 31, 32, 33, 34, 40, 41, 44, 48, 50, 51, 53, 54, 55, 59, 65, 66, 67, 68, 69, 70, 71, 72, 74, 75, 78, 84, 85, 91, 93, 95, 99}

    10403

    61077

    Returns: 47823

  24. {1, 2, 3, 9, 10, 15, 16, 22, 24, 25, 26, 28, 31, 34, 37, 40, 41, 42, 44, 45, 48, 50, 54, 56, 58, 64, 67, 68, 70, 71, 74, 75, 77, 78, 79, 80, 81, 82, 86, 87, 92, 95, 97, 98, 99}

    23194

    25638

    Returns: 2265

  25. {1, 6, 8, 10, 12, 15, 16, 17, 18, 21, 23, 26, 34, 35, 37, 39, 41, 42, 43, 44, 45, 46, 48, 50, 51, 52, 53, 58, 59, 60, 64, 66, 67, 68, 70, 74, 78, 79, 80, 83, 84, 87, 89, 91, 93, 97}

    14703

    90733

    Returns: 71851

  26. {1, 3, 6, 10, 11, 13, 15, 22, 25, 27, 28, 29, 33, 34, 35, 38, 39, 41, 42, 43, 44, 45, 46, 49, 50, 53, 54, 55, 58, 59, 60, 62, 64, 73, 77, 80, 82, 84, 85, 87, 88, 89, 91, 93, 95, 96, 98}

    29186

    65083

    Returns: 33362

  27. {1, 3, 4, 6, 7, 9, 13, 15, 16, 17, 19, 20, 23, 24, 29, 32, 33, 34, 38, 42, 45, 47, 48, 50, 51, 52, 56, 57, 60, 64, 67, 71, 72, 73, 76, 79, 80, 83, 85, 86, 87, 88, 89, 91, 92, 94, 95, 99}

    1410

    74384

    Returns: 69587

  28. {1, 6, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 25, 28, 31, 32, 33, 35, 36, 38, 39, 40, 41, 42, 43, 48, 51, 52, 55, 56, 58, 59, 60, 63, 65, 67, 69, 74, 75, 76, 80, 83, 84, 87, 90, 91, 95}

    42013

    84456

    Returns: 40126

  29. {1, 4, 5, 6, 10, 11, 12, 14, 15, 19, 20, 21, 24, 25, 26, 28, 29, 31, 33, 35, 38, 41, 42, 43, 46, 48, 49, 51, 53, 54, 55, 58, 63, 64, 69, 70, 71, 72, 74, 76, 82, 83, 85, 87, 89, 92, 93, 95, 96, 99}

    12910

    28661

    Returns: 15026

  30. {1, 3, 13, 22, 29, 31, 32, 36, 39, 42, 45, 47, 57, 61, 63, 66, 67, 75, 76, 79, 80, 81, 90, 92, 94, 95}

    11637

    47953

    Returns: 32874

  31. {1, 4, 11, 15, 20, 24, 28, 29, 30, 31, 32, 36, 38, 40, 43, 46, 51, 52, 55, 58, 60, 65, 69, 74, 85, 88, 91}

    45043

    92519

    Returns: 43070

  32. {1, 9, 10, 11, 21, 22, 26, 27, 28, 34, 37, 41, 48, 54, 55, 61, 66, 67, 71, 75, 76, 83, 85, 89, 92, 95, 96, 100}

    19862

    21037

    Returns: 1071

  33. {1, 5, 8, 11, 14, 16, 17, 21, 22, 25, 28, 30, 35, 43, 44, 51, 52, 60, 74, 77, 78, 80, 83, 84, 87, 88, 89, 91, 92}

    9295

    28649

    Returns: 17741

  34. {1, 7, 8, 9, 10, 15, 17, 20, 22, 28, 31, 37, 40, 41, 45, 46, 52, 53, 66, 68, 74, 82, 83, 84, 87, 88, 89, 94, 95, 96}

    1675

    47571

    Returns: 40998

  35. {1, 7, 12, 17, 18, 19, 23, 24, 28, 30, 33, 34, 42, 47, 49, 53, 54, 55, 57, 59, 61, 63, 66, 69, 70, 80, 81, 86, 90, 93, 99}

    28602

    97454

    Returns: 62348

  36. {1, 2, 5, 6, 9, 12, 13, 15, 22, 37, 43, 44, 52, 56, 64, 65, 66, 67, 72, 74, 75, 78, 79, 80, 81, 82, 87, 89, 90, 91, 96, 97}

    31862

    77865

    Returns: 41300

  37. {1, 2, 6, 7, 11, 15, 17, 24, 25, 26, 31, 32, 35, 38, 40, 42, 43, 44, 47, 49, 51, 57, 61, 66, 70, 78, 81, 83, 84, 87, 88, 90, 99}

    89053

    94014

    Returns: 4538

  38. {1, 5, 6, 9, 14, 16, 18, 20, 21, 24, 25, 29, 31, 34, 36, 38, 44, 47, 51, 52, 55, 57, 60, 65, 74, 76, 80, 81, 82, 84, 87, 88, 97, 100}

    8092

    14106

    Returns: 5513

  39. {1, 3, 6, 7, 8, 18, 20, 23, 24, 26, 37, 45, 46, 48, 54, 60, 61, 62, 63, 64, 68, 73, 74, 75, 76, 79, 80, 82, 85, 91, 92, 93, 94, 97, 98}

    25489

    94977

    Returns: 64675

  40. {1, 5, 6, 8, 9, 15, 23, 25, 26, 32, 33, 34, 39, 41, 42, 43, 46, 48, 52, 53, 54, 55, 56, 59, 62, 63, 71, 77, 80, 85, 86, 90, 92, 93, 96, 100}

    48543

    62216

    Returns: 12410

  41. {1, 5, 8, 9, 12, 13, 15, 19, 25, 28, 30, 32, 33, 34, 36, 37, 38, 39, 40, 44, 45, 55, 58, 60, 62, 71, 72, 74, 75, 79, 82, 86, 88, 89, 95, 96, 98}

    23669

    76075

    Returns: 47551

  42. {1, 13, 14, 15, 17, 18, 25, 26, 27, 28, 37, 38, 40, 45, 46, 48, 50, 52, 55, 58, 59, 62, 64, 65, 66, 68, 69, 70, 71, 77, 78, 81, 92, 93, 95, 96, 97, 99}

    39537

    60590

    Returns: 19717

  43. {1, 3, 7, 8, 12, 13, 15, 16, 17, 18, 23, 26, 27, 30, 35, 36, 37, 40, 42, 45, 47, 49, 50, 51, 52, 56, 59, 64, 66, 68, 70, 73, 76, 79, 82, 83, 88, 95, 99}

    2350

    2506

    Returns: 137

  44. {1, 3, 5, 7, 14, 19, 20, 23, 27, 28, 34, 38, 41, 42, 46, 47, 48, 49, 50, 51, 58, 63, 65, 66, 67, 68, 70, 75, 76, 79, 82, 84, 86, 87, 90, 93, 94, 95, 98, 99}

    23765

    94308

    Returns: 66138

  45. {1, 2, 3, 7, 8, 11, 14, 15, 16, 18, 19, 20, 22, 24, 28, 30, 31, 32, 35, 37, 38, 47, 48, 50, 58, 62, 63, 64, 65, 68, 73, 76, 78, 79, 81, 82, 88, 93, 94, 97, 98}

    2536

    16731

    Returns: 13194

  46. {1, 3, 9, 12, 13, 16, 17, 18, 19, 21, 24, 27, 28, 30, 31, 34, 36, 38, 41, 42, 43, 44, 45, 47, 49, 53, 64, 65, 67, 68, 70, 74, 76, 77, 79, 83, 84, 92, 94, 95, 96, 100}

    3329

    16538

    Returns: 12082

  47. {1, 6, 7, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 32, 36, 39, 41, 43, 51, 52, 54, 60, 64, 65, 67, 68, 69, 71, 73, 74, 75, 79, 80, 84, 87, 88, 90, 91, 92, 94, 95, 97, 100}

    56028

    70489

    Returns: 13419

  48. {1, 8, 11, 15, 16, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 37, 38, 39, 45, 47, 50, 55, 57, 60, 61, 63, 64, 65, 66, 67, 68, 70, 71, 75, 77, 78, 79, 81, 89, 91, 92, 97, 98, 99}

    19614

    35393

    Returns: 14708

  49. {1, 4, 5, 10, 12, 13, 14, 15, 16, 20, 21, 23, 24, 35, 37, 38, 40, 44, 47, 48, 49, 54, 55, 56, 58, 60, 63, 66, 67, 68, 71, 75, 78, 79, 85, 88, 89, 90, 92, 95, 96, 97, 98, 99, 100}

    8552

    44923

    Returns: 33711

  50. {1, 6, 12, 14, 15, 16, 19, 20, 21, 23, 25, 27, 30, 31, 32, 36, 37, 39, 40, 42, 44, 47, 48, 50, 53, 55, 60, 61, 70, 71, 72, 76, 78, 79, 80, 81, 84, 85, 86, 87, 90, 93, 94, 95, 98, 100}

    26216

    36445

    Returns: 9660

  51. {1, 2, 3, 5, 8, 9, 12, 13, 14, 15, 16, 18, 19, 22, 25, 35, 37, 39, 40, 43, 47, 48, 51, 52, 57, 58, 63, 64, 66, 68, 69, 74, 75, 78, 79, 80, 82, 83, 84, 90, 91, 92, 93, 95, 98, 99, 100}

    33220

    47401

    Returns: 13247

  52. {1, 11, 12, 15, 17, 18, 20, 25, 27, 30, 31, 33, 35, 37, 43, 45, 46, 47, 48, 50, 53, 55, 56, 60, 61, 64, 66, 67, 68, 72, 74, 75, 78, 79, 81, 82, 84, 86, 87, 88, 89, 90, 91, 93, 95, 96, 98, 100}

    15693

    20038

    Returns: 4093

  53. {1, 9, 11, 12, 13, 15, 18, 19, 20, 22, 24, 29, 33, 36, 38, 40, 42, 43, 45, 48, 49, 51, 53, 55, 60, 61, 64, 65, 66, 68, 69, 72, 75, 78, 79, 80, 83, 84, 85, 86, 88, 89, 90, 91, 95, 97, 98, 99, 100}

    38331

    38558

    Returns: 216

  54. {1, 2, 3, 4, 9, 11, 12, 15, 17, 18, 19, 20, 26, 32, 33, 34, 35, 37, 39, 41, 43, 44, 47, 55, 57, 58, 59, 62, 63, 65, 66, 67, 71, 73, 74, 75, 76, 77, 78, 79, 80, 82, 85, 86, 87, 90, 93, 95, 99, 100}

    2913

    67162

    Returns: 61292

  55. {1, 2, 6, 8, 14, 16, 20, 21, 31, 35, 38, 47, 50, 52, 56, 57, 72, 73, 75, 77, 78, 79, 81, 84, 90, 96}

    8062

    16449

    Returns: 7612

  56. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}

    1

    100000

    Returns: 98040

  57. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 100}

    1

    100000

    Returns: 98020

  58. {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99}

    1

    100000

    Returns: 50000

  59. {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99}

    50000

    50007

    Returns: 4

  60. {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99}

    9999

    99999

    Returns: 45001

  61. {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99}

    999

    99999

    Returns: 49501

  62. {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98}

    1

    100000

    Returns: 98000

  63. {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98}

    1

    1000

    Returns: 980

  64. {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98}

    353

    35353

    Returns: 34301

  65. {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98}

    99999

    100000

    Returns: 1

  66. {1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99}

    1

    100000

    Returns: 97058

  67. {1 }

    1

    100000

    Returns: 50000

  68. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    1

    100000

    Returns: 98040

  69. {1 }

    1000

    1000

    Returns: 0

  70. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    1

    100000

    Returns: 90910

  71. {1, 3, 7, 19 }

    1

    100000

    Returns: 50000

  72. {1 }

    100000

    100000

    Returns: 0

  73. {1, 2 }

    1

    100000

    Returns: 66667

  74. {1 }

    1

    100000

    Returns: 50000

  75. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    1

    100000

    Returns: 98040

  76. {1 }

    1000

    1000

    Returns: 0

  77. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    1

    100000

    Returns: 90910

  78. {1, 3, 7, 19 }

    1

    100000

    Returns: 50000

  79. {1 }

    100000

    100000

    Returns: 0

  80. {1, 2 }

    1

    100000

    Returns: 66667

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: