Statistics

Problem Statement for "PScores"

Problem Statement

A game is played as follows. The player is given a number p (his current p-value) between 0 and N-1 inclusive, where N is the number of elements in nexts. The following steps are then repeated until the game ends:
  1. Look at nexts[p]. If the player has already had nexts[p] earlier in the game, the game is over, and his score is p.
  2. Otherwise, the current p-value is changed to nexts[p].
Return the number of distinct initial p-values that would result in the given final score.

Definition

Class:
PScores
Method:
howMany
Parameters:
int[], int
Returns:
int
Method signature:
int howMany(int[] nexts, int score)
(be sure your method is public)

Constraints

  • nexts will contain between 1 and 50 elements inclusive.
  • Each element of nexts will be between 0 and N-1 inclusive, where N is the number of elements in nexts.
  • score will be between 0 and N-1 inclusive, where N is the number of elements in nexts.

Examples

  1. {28,7,37,31,26,21,35,23,21,10,7,11,16,16,32,11,37,15,31,10,35,14,22,32,28,17,37,21,24,7,1,18,32,1,18,22,32,23}

    30

    Returns: 0

  2. {28,18,24,26,13,32,34,4,32,4,23,35,11,3,16,6,17,30,26,15,35,38,33,19,17,28,5,31,20,14,5,27,33,30,3,37,7,6,20}

    30

    Returns: 26

  3. {5,23,27,14,15,27,26,26,26,7,17,22,25,11,16,11,18,14,17,14,6,25,17,18,18,17,15,24,12,26}

    27

    Returns: 0

  4. {10,24,14,3,2,24,13,3,20,2,7,16,5,29,27,0,29,9,2,17,12,23,18,13,29,11,19,2,19,20}

    10

    Returns: 0

  5. {7,24,17,34,0,8,12,7,10,24,38,31,28,14,35,27,39,1,23,34,27,29,37,10,8,38,16,13,30,3,24,26,36,20,6,0,23,30,37,13}

    38

    Returns: 2

  6. {22,0,5,19,40,12,34,40,48,43,16,12,1,18,43,13,1,42,8,15,19,29,39,41,27,23,45,24,17,39,2,32,14,1,4,45,15,7,22,22,26,13,23,1,44,41,43,0,15}

    43

    Returns: 0

  7. {46,31,2,20,35,18,2,36,30,42,24,21,36,9,21,13,3,41,17,24,40,31,25,24,17,19,37,43,18,17,29,43,1,28,36,31,0,36,34,28,35,3,11,37,6,10,23,8}

    31

    Returns: 2

  8. {37,30,20,6,2,34,35,33,5,5,0,26,27,26,32,4,29,10,17,3,15,3,2,35,34,27,35,19,33,7,34,0,27,2,23,27,20,5,28}

    29

    Returns: 0

  9. {1,1,11,33,1,16,22,21,26,10,39,37,30,11,10,6,15,16,3,2,10,11,38,41,13,36,18,18,6,21,0,13,27,27,7,15,6,3,13,23,27,33,19}

    0

    Returns: 0

  10. {10,23,11,10,1,39,36,16,36,5,33,8,0,35,32,21,5,6,8,36,26,10,38,36,13,17,7,3,23,37,4,24,12,37,11,7,30,24,11,33}

    36

    Returns: 1

  11. {28,6,20,12,20,29,19,2,43,17,23,7,26,26,38,26,27,43,27,26,33,43,22,6,7,32,24,20,1,44,48,34,15,5,44,35,47,7,1,27,48,1,11,25,48,12,28,37,45}

    1

    Returns: 0

  12. {15,10,10,7,7,17,10,34,22,11,27,21,8,28,10,30,7,27,31,34,28,21,23,10,17,2,19,34,21,5,16,22,34,31,16,11}

    3

    Returns: 0

  13. {24,25,16,3,0,0,14,23,15,19,6,12,26,27,11,18,32,25,16,20,8,2,31,17,9,33,12,33,24,33,22,14,17,17}

    18

    Returns: 0

  14. {22,33,38,42,40,40,3,37,45,35,38,14,22,23,6,33,17,1,26,34,11,10,21,30,32,12,39,8,27,32,15,24,31,15,41,17,24,2,17,39,33,17,42,40,16,20}

    25

    Returns: 0

  15. {28,11,33,12,20,16,28,9,32,25,9,25,25,6,6,36,2,11,2,26,9,29,24,19,22,2,8,0,22,25,31,5,2,7,18,35,24,22,25}

    23

    Returns: 0

  16. {0,16,4,0,7,9,1,21,8,10,15,14,18,3,24,29,11,18,18,9,11,20,13,10,23,21,6,18,20,6}

    17

    Returns: 0

  17. {30,36,19,28,9,15,43,19,22,5,41,2,28,8,4,0,3,1,25,26,31,28,36,18,39,36,2,28,1,30,31,33,39,19,43,16,25,30,31,33,20,6,43,16,7}

    29

    Returns: 0

  18. {8,19,2,16,6,20,2,14,17,11,14,12,14,14,18,23,2,8,19,16,15,1,12,14,12}

    23

    Returns: 0

  19. {29,27,42,15,12,24,22,9,34,6,19,36,38,15,5,13,23,6,31,34,9,26,10,34,20,40,23,0,29,22,7,23,6,19,25,12,20,24,4,2,15,17,21,38}

    40

    Returns: 0

  20. {2,37,28,35,10,12,18,31,8,33,28,7,16,18,20,15,8,35,37,31,36,22,36,18,34,37,6,6,37,12,5,35,0,22,15,2,28,1}

    25

    Returns: 0

  21. {36,14,18,37,6,6,9,40,34,14,38,6,10,3,17,21,39,0,7,25,9,29,1,32,24,30,29,29,31,23,20,27,17,27,27,25,39,40,24,21,11}

    17

    Returns: 1

  22. {24,43,41,9,15,2,33,43,44,7,20,40,29,45,34,18,16,37,0,32,17,21,9,28,36,45,34,32,24,22,24,30,20,13,20,11,19,19,38,37,40,6,23,42,43,29}

    22

    Returns: 0

  23. {23,8,12,15,3,8,8,21,27,17,14,18,24,23,19,1,18,27,18,4,33,12,17,30,9,26,18,26,14,13,3,28,11,15}

    12

    Returns: 0

  24. {9,23,5,12,6,13,20,5,2,23,23,22,19,3,21,7,21,9,11,22,3,4,24,24,24}

    20

    Returns: 0

  25. {19,16,14,19,26,22,12,1,5,19,19,15,32,16,8,28,8,26,10,20,26,27,12,26,11,21,9,22,31,28,26,25,16,27}

    14

    Returns: 0

  26. {9,6,32,35,14,22,25,23,30,9,20,33,17,16,34,17,33,1,2,18,2,25,20,17,34,27,9,23,10,30,2,25,27,38,13,8,36,31,26}

    27

    Returns: 2

  27. {3,7,16,18,17,19,20,4,26,0,28,27,10,25,7,15,11,10,10,16,2,9,14,23,14,24,24,1,16}

    26

    Returns: 0

  28. {2,12,3,18,5,12,14,19,0,23,8,22,20,3,22,8,11,17,19,9,3,10,8,7,10}

    24

    Returns: 0

  29. {13,18,14,20,9,5,20,0,13,0,19,18,17,23,4,3,7,17,18,4,18,1,10,8,16}

    11

    Returns: 0

  30. {26,3,31,17,3,20,31,28,1,13,14,10,33,31,5,8,28,9,19,15,2,25,11,27,2,33,23,24,23,7,19,22,6,7}

    22

    Returns: 1

  31. {0,1}

    0

    Returns: 1

    Each player begins the game, and then has no place to go, so the game ends. Only the player that initially receives 0 has score 0.

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

    3

    Returns: 1

    The player who starts with 4 will travel all the way around, and finally end up with score 3.

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

    0

    Returns: 14

    The score 0 is popular.

  34. {2,2,0}

    0

    Returns: 2

    Players that initially receive 1 or 2 will end up with score 0.

  35. {0,11,25,29,9,18,0,3,18,19,6,23,25,6,3,9,2,26,10,4,14,10,20,23,26,23,6,16,12,24}

    23

    Returns: 9

  36. {22,18,29,15,25,4,15,33,42,31,15,41,39,24,21,25,14,38,2,12,7,14,27,41,16,34,9,33,14,44,42,30,31,19,37,21,38,44,30,38,19,30,41,34,17}

    34

    Returns: 0

  37. {15,2,1,22,3,11,19,10,1,2,14,3,0,12,21,18,0,2,11,5,0,9,4,19,1}

    4

    Returns: 13

  38. {11,26,14,28,22,6,29,18,27,21,26,12,13,14,31,10,20,27,30,32,18,27,16,30,30,13,12,19,24,16,13,14,1}

    32

    Returns: 0

  39. {14,19,13,23,11,9,8,3,7,20,20,22,17,15,9,16,18,24,15,0,18,3,5,26,6,8,2,17}

    10

    Returns: 0

  40. {19,21,27,2,23,0,27,16,27,25,3,1,6,29,4,6,8,22,26,20,3,7,25,5,24,11,25,12,29,19}

    18

    Returns: 0

  41. {15,19,16,8,13,16,15,10,6,8,18,3,11,9,13,15,12,7,9,10,20,17,14,25,8,18}

    6

    Returns: 0

  42. {0,12,24,5,21,25,25,10,13,22,25,3,28,10,22,0,27,3,5,24,8,12,26,30,19,14,5,15,18,8,14}

    2

    Returns: 0

  43. {16,40,8,24,9,32,23,4,33,25,41,40,2,34,45,3,32,40,42,17,21,33,44,5,12,18,30,31,37,31,43,41,38,20,28,10,45,14,14,26,40,11,40,32,3,23}

    15

    Returns: 0

  44. {38,2,0,45,13,38,16,45,29,14,18,18,29,39,3,4,4,24,6,35,12,15,42,20,14,8,17,22,37,21,46,47,39,35,18,42,20,23,5,5,7,33,45,13,2,2,37,5}

    39

    Returns: 0

  45. {28,11,26,12,33,33,22,29,9,23,34,14,13,22,19,19,3,13,33,0,18,9,16,25,20,22,11,23,21,19,2,31,32,4,19}

    15

    Returns: 0

  46. {16,22,19,20,14,17,19,1,19,23,1,21,20,7,1,7,10,0,19,7,0,9,9,18,0}

    0

    Returns: 0

  47. {31,6,9,27,38,34,22,18,26,24,16,26,29,13,12,11,33,28,17,27,4,21,13,21,42,32,4,21,19,22,20,1,30,22,1,3,7,30,28,22,29,5,3}

    9

    Returns: 0

  48. {16,21,12,28,28,7,0,15,24,9,8,21,23,0,23,6,5,5,20,25,25,13,3,10,20,25,14,0,16,7}

    27

    Returns: 0

  49. {3,25,2,33,33,13,8,1,6,9,29,16,37,26,6,26,3,30,2,19,36,4,32,39,24,27,6,14,19,19,4,10,31,28,13,37,8,32,19,11,16}

    15

    Returns: 0

  50. {22,6,36,40,39,17,19,27,38,24,27,23,39,25,39,34,0,7,24,17,12,1,1,22,0,1,18,8,27,20,18,6,13,13,36,15,19,39,32,33,36,6}

    3

    Returns: 0

  51. {9,4,2,11,5,11,0,10,15,11,14,26,8,13,4,26,4,10,24,24,2,25,22,24,18,19,18,11,19}

    17

    Returns: 0

  52. {1,10,4,16,32,13,15,17,33,9,8,10,24,32,17,22,20,12,16,17,23,23,3,10,9,2,21,10,10,34,12,10,15,7,10}

    19

    Returns: 0

  53. {6,6,26,32,25,31,0,13,27,26,11,13,26,7,27,21,19,17,25,32,29,6,13,21,24,9,5,17,2,7,23,23,1,29,25}

    25

    Returns: 0

  54. {29,21,13,20,18,16,10,11,30,24,30,22,13,8,32,9,13,3,13,3,24,15,32,9,34,18,20,25,18,30,10,26,10,31,22}

    34

    Returns: 0

  55. {17,9,10,20,6,6,23,20,6,27,19,15,19,17,6,1,6,9,14,14,19,19,18,11,21,20,13,28,1}

    25

    Returns: 0

  56. {19,8,25,15,7,5,17,13,9,5,28,14,9,9,5,16,14,29,20,27,3,11,24,16,23,30,4,12,3,20,22,5}

    2

    Returns: 0

  57. {39,38,41,3,38,5,5,22,15,24,25,39,26,35,28,14,34,16,5,30,42,20,28,5,10,8,36,28,13,23,15,20,25,0,42,15,11,0,1,41,30,5,10,28}

    22

    Returns: 0

  58. {5,32,23,19,27,25,32,4,20,12,20,3,17,31,7,2,30,7,19,11,11,25,10,30,16,27,29,6,16,9,18,6,28}

    22

    Returns: 0

  59. {24,30,18,19,8,27,31,23,31,30,34,13,22,23,35,30,16,11,6,31,0,34,2,14,36,1,34,26,3,20,8,3,10,10,1,38,1,24,18}

    8

    Returns: 0

  60. {14,4,10,35,18,24,35,3,36,16,18,29,30,39,5,3,43,1,21,4,37,21,18,16,42,19,28,34,16,16,22,45,13,37,29,15,21,7,28,6,17,15,39,17,9,2,4}

    17

    Returns: 0

  61. {29,26,27,15,20,29,18,25,10,19,7,27,28,31,30,29,0,12,7,16,17,4,3,13,24,12,14,18,23,28,17,27,26}

    29

    Returns: 0

  62. {37,39,23,15,25,45,28,39,44,12,23,21,47,16,15,7,12,31,46,16,12,28,15,9,27,30,25,20,33,0,18,28,11,45,3,43,43,39,22,46,41,33,10,27,17,35,32,17}

    20

    Returns: 9

  63. {15,8,39,5,33,2,12,21,35,13,28,30,29,25,19,20,7,41,17,32,10,2,20,8,34,41,31,29,25,26,26,4,38,31,40,4,3,21,28,2,23,23}

    30

    Returns: 0

  64. {30,12,13,2,30,6,12,10,14,25,5,1,1,31,20,21,32,20,26,8,20,16,16,5,25,18,8,18,5,15,13,33,13,13}

    25

    Returns: 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: