Statistics

Problem Statement for "Apocalypse"

Problem Statement

We have an undirected tree with n nodes, numbered 0 through n-1. You are given its description: a int[] p with n-1 elements. For each valid i, there is an edge between nodes p[i] and (i+1).

There are k tokens on the tree, each in a different node. You are given a int[] position. The elements of position are the numbers of the nodes that contain the tokens.

A demon has placed k bombs onto the tree: one bomb into each node that currently contains a token. The bombs will all explode after t turns. If there is a token in a node with a bomb when the bomb explodes, the token is destroyed. Your task is to save as many tokens as possible.

In each turn you can move each token at most once: from its current node to any adjacent node. Whenever you move a token, the destination node must be empty. In other words, each node must always contain at most one token. You get to choose the order in which to move the tokens, and the order may be different in different turns.

Compute and return the maximal number of tokens saved from the explosions.

Definition

Class:
Apocalypse
Method:
maximalSurvival
Parameters:
int[], int[], int
Returns:
int
Method signature:
int maximalSurvival(int[] p, int[] position, int t)
(be sure your method is public)

Constraints

  • n will be between 2 and 50, inclusive.
  • p will contain exactly n-1 elements.
  • For each i, 0 <= p[i] <= i.
  • position will contain between 1 and n elements, inclusive.
  • Each element in position will be between 0 and n-1, inclusive.
  • Elements in position will be distinct.
  • t will be between 1 and 50, inclusive.

Examples

  1. {0,1,2}

    {2,3}

    1

    Returns: 1

    The tree is a line: 0 - 1 - 2 - 3. Initially, the tokens and the bombs are in the nodes 2 and 3. We have only one turn. Whatever we do, the token that starts on node 3 will be destroyed. We can save the other token by moving it from node 2 to node 1.

  2. {0,1,2}

    {2,3}

    2

    Returns: 2

    This is the same setting as in Example 0, but now we have two turns. Now we can save both tokens. In the first turn we first move the token from node 2 to node 1 and only then we move the token from node 3 to node 2 (which is now empty). In the second turn we move both tokens again: from 1 to 0 and then from 2 to 1.

  3. {0,0,0,1,2,3}

    {1,2,3}

    1

    Returns: 3

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

    {0,1,2,3,4,5,6}

    50

    Returns: 4

  5. {0}

    {0,1}

    1

    Returns: 0

  6. {0,0,0,0,0}

    {0,1,2}

    2

    Returns: 2

  7. {0, 0, 1, 0, 0, 3, 3, 2, 1, 1, 3, 3, 2, 0, 0, 1, 3, 1, 2}

    {13, 0, 5, 18, 4, 14, 7, 12}

    6

    Returns: 8

  8. {0, 0, 0, 2, 4, 4, 4, 7, 6, 8, 9, 10, 11, 11, 13, 14, 15, 16, 18, 18, 20, 21, 22, 23, 22, 25, 24, 26, 28, 29, 29, 29, 31, 31, 34, 35, 35, 36, 36, 37, 39, 39, 40, 42, 42, 45, 46}

    {14, 3, 10, 33, 38, 18, 15, 34, 31, 20, 0, 30, 16, 44, 12, 7, 17, 37, 22, 39, 21, 27, 25, 41, 26, 35, 32, 36, 46, 19, 1, 47, 28, 9, 4, 24, 23, 2, 40}

    6

    Returns: 9

  9. {0, 1, 0, 3, 2, 1, 2, 3, 0, 2, 1, 2}

    {9, 5, 12, 1, 4, 7, 8, 0}

    46

    Returns: 5

  10. {0, 1, 2, 2, 2, 5, 5, 7, 6, 9, 10, 9, 12, 11, 12, 15, 16, 17, 16, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 29, 30, 31, 31, 33, 33, 34, 36, 37, 37}

    {38, 16, 5, 20, 19, 8, 2, 6, 31, 15, 14, 26, 36, 17, 18, 23, 35, 27, 12, 40, 25, 22, 13, 4}

    17

    Returns: 17

  11. {0, 0, 2, 1, 1, 0, 0, 2, 0, 3, 1, 2, 2, 3, 2, 2, 2, 2, 3, 3, 1, 1, 3, 1, 0, 2, 1, 0, 0, 1, 2, 0, 3, 0, 0, 0, 1, 1, 3, 2, 2, 0, 2, 3, 1, 2, 2, 3}

    {31, 42, 11, 7, 29, 15, 23, 8, 25, 46, 43, 20, 44, 12, 28, 1, 13, 37, 2, 21, 34, 9, 45, 22, 4, 47, 32, 39}

    10

    Returns: 21

  12. {0, 0, 1, 3, 3, 4, 4, 6, 6}

    {9, 6, 0, 1}

    29

    Returns: 4

  13. {0, 0, 0, 1, 2, 1, 3, 2, 0, 1, 3, 3, 3, 0, 1, 0, 2, 0, 0, 3, 1}

    {17}

    40

    Returns: 1

  14. {0, 0, 0, 0, 3, 2, 1, 2, 3, 0, 2, 3, 3, 2, 2, 2, 2, 2, 1, 2, 0, 1, 2, 1, 1, 2, 3, 0}

    {14, 10, 18, 1, 11, 20, 13, 15, 26, 0, 21, 5}

    6

    Returns: 12

  15. {0, 0, 1, 2, 4, 4, 4, 5, 6, 8, 10, 9, 12, 11, 13, 13, 15, 17, 17, 18, 20, 20, 22, 23, 23, 25, 25, 27, 28, 29, 30, 31, 32, 32, 34, 35, 35, 35, 38, 38, 38, 41, 41, 43, 42, 45}

    {29, 13, 41, 39, 24, 40, 36, 17, 3, 1, 23, 6, 43, 0, 9, 8, 21, 27, 18, 11, 33, 4, 28, 12, 22, 35, 20, 44, 37, 32, 45, 38, 30, 5, 34, 15, 31, 7, 14, 16, 25, 2}

    4

    Returns: 5

  16. {0, 0, 0, 3, 0, 0, 3, 1, 2, 0, 0, 2, 2, 2, 1, 2, 3, 1, 3, 1, 0, 2, 2, 2, 1}

    {0, 18, 22, 16, 10, 11, 23, 21, 8, 25, 9, 20, 15, 6, 4, 2, 7, 19, 17, 24, 12, 13}

    5

    Returns: 4

  17. {0, 0, 0, 0, 2, 3, 1, 1, 2, 3, 0, 2, 1, 0, 0, 2, 3, 1, 0, 2, 1, 1, 1, 2, 3, 2, 3, 1, 1, 0, 1, 3, 3, 0, 3}

    {16, 28, 20, 3, 25, 29, 5, 11, 8, 34, 14, 15, 35, 26, 21, 23, 22, 9}

    29

    Returns: 18

  18. {0, 1, 0, 3, 4, 3, 4, 7, 6, 7, 8, 10, 12, 13, 12, 13, 16, 17, 18, 19, 20, 21, 22, 22, 24, 23, 26, 27, 27, 29, 30, 29, 30, 33, 34, 34, 35, 36, 37, 38, 39, 40, 41, 43, 43, 45}

    {27, 41, 37, 13, 25, 34, 45, 15, 2, 36, 3, 19, 44, 32, 26, 16, 14, 29, 10, 8, 7, 22, 4, 5, 33, 42, 6, 18, 0, 12, 20, 31, 9}

    25

    Returns: 14

  19. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {16, 15, 28, 22}

    19

    Returns: 4

  20. {0, 0, 2, 3, 3, 3, 4, 5, 7, 9, 9, 9, 10, 13}

    {0, 11}

    3

    Returns: 2

  21. {0, 1, 1, 3, 0, 3, 1, 3, 0, 3, 3, 2, 1, 2, 2, 2, 3, 3, 3, 0, 0, 3, 1, 3, 3, 0}

    {19, 24, 1, 15, 0, 17, 18, 10, 23, 26, 20, 2}

    10

    Returns: 12

  22. {0, 0, 2, 2, 2, 5, 5}

    {6, 5, 0, 4, 2, 3, 7}

    8

    Returns: 1

  23. {0, 0}

    {0, 2, 1}

    2

    Returns: 0

  24. {0, 1, 1, 3, 0, 3, 2, 0, 3, 0, 0, 2, 0, 2, 3, 3, 3, 1, 2, 3, 2, 0, 1, 0, 1, 2, 1, 2, 1, 2, 3}

    {5, 6, 12}

    50

    Returns: 3

  25. {0, 0, 2, 1, 4, 4, 4, 5, 6, 8, 10, 9}

    {8, 12, 6, 10, 0, 7, 5, 4, 2, 11}

    3

    Returns: 3

  26. {0, 1, 1, 1, 1, 0, 3, 3, 2, 2, 1, 2, 0, 2, 0, 2, 3, 2, 1, 0, 0, 2, 3, 0, 2, 0, 0, 0}

    {24, 6, 9, 5, 3, 20, 12, 17, 14, 25}

    28

    Returns: 10

  27. {0, 1, 0, 1, 4, 5, 5, 6, 8, 7, 10, 9, 12, 12, 12, 13, 15, 17, 16, 17, 19, 20, 22, 23, 22, 23, 24, 25, 27, 28, 29, 29, 31, 32, 33, 33, 36, 37, 38, 37, 40, 41, 40, 41, 44, 43, 46}

    {1, 2, 19, 46, 37, 21, 24, 23, 31, 5, 17, 30, 28, 47, 41, 32, 43, 18, 26, 27, 3, 35, 34, 45, 12, 0, 4}

    6

    Returns: 21

  28. {0, 0, 2, 2, 2, 5, 6, 7, 7, 7, 8, 10, 11, 13, 12, 15, 14, 16, 17}

    {19, 8, 4, 2, 7, 5, 17}

    44

    Returns: 7

  29. {0, 1, 1, 3, 3, 1, 2, 3, 2, 2, 0, 1, 0, 3, 3, 0, 3}

    {3, 16, 0, 9, 17, 5, 2, 7}

    9

    Returns: 8

  30. {0, 1, 0, 0, 1, 1, 0, 3, 2, 3, 2, 2, 3, 1, 2, 3, 1, 1, 1, 1, 0, 0, 0, 0, 2, 1, 0, 1, 0}

    {20, 3, 22, 16, 21, 28, 5, 2}

    18

    Returns: 8

  31. {0, 0, 1, 3, 2, 3, 4, 7, 8, 9, 8, 10, 11, 13, 12}

    {1}

    10

    Returns: 1

  32. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {2, 4, 21, 9, 10, 7, 12, 19, 1, 17, 29, 18, 6, 8, 11, 15, 25, 14, 13, 28, 22, 3, 27, 5, 26, 38, 23, 0, 36, 33, 37, 31, 32, 34, 35, 16, 30, 24}

    9

    Returns: 1

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

    {12, 17, 5, 36, 2}

    7

    Returns: 5

  34. {0, 1, 1, 3, 4, 4, 4, 5, 7, 8, 10, 11, 11, 13, 13, 14, 15, 15, 16, 18, 20, 21, 20, 23, 22, 23, 24, 25, 27, 27, 29, 31}

    {14, 17, 7, 2, 22, 16, 26, 12, 29, 23, 4, 11, 5, 20, 31, 6, 3, 27, 19, 8, 15, 10, 0, 32, 1, 25, 21, 18, 30, 24, 28, 9}

    29

    Returns: 1

  35. {0, 0, 1, 3, 0, 3, 2, 1, 3}

    {4, 0, 7, 5, 3, 8, 9}

    3

    Returns: 3

  36. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {17}

    10

    Returns: 1

  37. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {15, 12}

    7

    Returns: 2

  38. {0, 0, 0, 0, 0, 0, 0}

    {0, 7, 5, 2, 1, 3}

    3

    Returns: 2

  39. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

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

    5

    Returns: 5

  40. {0, 0, 0, 0, 0}

    {5, 1, 4, 3, 2, 0}

    46

    Returns: 0

  41. {0, 0, 0, 0}

    {2, 4, 0}

    3

    Returns: 2

  42. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {30, 18, 19, 1, 33, 0, 32, 8, 40, 10, 17, 20, 37, 4, 36, 13, 14, 22, 9}

    3

    Returns: 3

  43. {0, 1, 0, 2, 3, 3, 4, 6, 7, 9, 8, 10, 10, 12, 13, 15, 15, 15, 18, 18, 19, 19, 20, 23, 23, 25, 26, 27, 28, 27, 29, 31, 31, 31, 33, 34, 36, 35, 36, 37, 38, 41, 42, 41, 42, 44}

    {3, 31, 10, 36, 28, 12, 8, 13, 6, 9, 0, 14, 37, 7, 19, 22, 34, 20, 2, 46, 45, 42, 30, 26, 4, 35, 43, 5, 32, 38, 1, 24, 44, 23, 15, 41, 27, 16}

    6

    Returns: 9

  44. {0, 1, 1, 2}

    {0}

    20

    Returns: 1

  45. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {27, 30, 24, 40, 37, 35, 10, 28, 6, 38}

    9

    Returns: 9

  46. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {29, 25, 4, 12, 14, 7, 16}

    9

    Returns: 7

  47. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {0, 14, 3, 8, 5}

    10

    Returns: 5

  48. {0, 1, 0, 3, 3, 0, 2, 1, 0, 1, 2, 0, 0, 3, 2, 0, 3, 2, 1}

    {14, 18}

    5

    Returns: 2

  49. {0, 1, 1, 1, 3, 4, 4, 5, 8, 9, 8, 9, 11, 11, 13, 13, 15, 15, 17, 17, 18, 20, 20, 22, 24, 23, 24, 26, 28, 28, 29, 29, 32, 31}

    {11, 27, 5, 30, 25, 29, 28, 20, 4, 13, 21, 33, 1, 8, 22, 23, 18, 14, 16, 3, 7, 31, 26}

    8

    Returns: 12

  50. {0, 0, 2, 3, 0, 2, 2, 2, 0, 2, 3, 0, 1, 1, 3, 0, 1, 3, 0, 3, 1, 2, 1, 0, 1, 2, 3, 0, 1, 1, 3, 1, 3, 3, 2, 0, 2, 2, 1, 2, 3}

    {16, 21, 4, 30, 17, 25, 31, 1, 40, 23, 22, 0, 20, 15, 12, 26, 35, 6, 2, 5, 13, 9, 18}

    28

    Returns: 19

  51. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {1, 15}

    10

    Returns: 2

  52. {0, 0, 2, 2}

    {3}

    8

    Returns: 1

  53. {0, 0, 2, 2, 4, 4, 6, 7, 8, 7, 9, 9, 11, 12, 13, 15, 14, 17, 16, 18, 18, 21, 20, 21, 23, 24, 25, 26, 27, 28, 28, 29, 30, 32, 32, 34, 35}

    {20, 7, 31, 28, 6}

    12

    Returns: 5

  54. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {7, 0, 5, 18, 22, 26, 25, 6, 11, 19, 28, 31, 14, 29, 20, 3, 1, 21, 27}

    5

    Returns: 5

  55. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {32, 44, 11, 6, 25, 27, 17, 46, 45, 1, 38}

    9

    Returns: 9

  56. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {9, 0, 10, 7, 3, 13}

    14

    Returns: 6

  57. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {1, 23, 21, 0, 6, 8, 20, 16}

    6

    Returns: 6

  58. {0, 0, 0, 0, 3, 3, 3, 0}

    {3}

    5

    Returns: 1

  59. {0, 1, 1, 3, 3, 0, 1, 0, 2, 2, 3, 2, 3, 1, 1, 1, 3, 2, 3, 0, 0}

    {8, 19, 6, 14, 2, 18, 3, 13, 4, 10, 21}

    9

    Returns: 11

  60. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {12, 8, 0, 10, 7, 5, 9, 6, 14}

    9

    Returns: 6

  61. {0}

    {0}

    42

    Returns: 1

  62. {0, 1, 1, 3, 3, 3, 0, 2, 3, 3, 2, 1, 3, 0, 0, 3, 1, 1, 1, 1, 2, 2, 3, 0, 0, 2, 0, 3, 2, 0, 1, 1, 3, 2, 3, 1, 3, 1, 3, 0, 1, 2, 0, 1, 0, 2, 2, 3}

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

    3

    Returns: 6

  63. {0, 0, 0, 0, 0}

    {2}

    8

    Returns: 1

  64. {0, 1, 0, 1, 1, 3, 2, 2, 1, 3, 3, 0, 3, 1, 2, 1, 0, 2, 2, 3, 1, 0, 1, 1, 2, 0}

    {0, 20, 21, 5, 18, 24, 7, 1, 6, 15, 26}

    23

    Returns: 11

  65. {0, 0, 0, 1, 0, 3, 3, 3, 2, 0, 0, 3, 3, 1, 1, 2}

    {9, 4, 8, 2, 6, 10, 14, 16, 12, 0, 7, 13, 5, 15, 1}

    6

    Returns: 2

  66. {0, 1, 1, 2, 3, 5, 5, 6, 6, 8, 9, 9, 10, 13, 13, 15, 15, 17, 18, 18, 20, 20, 22, 22, 23, 23, 24, 27, 26, 28, 30, 30, 31, 32, 34, 35, 34, 35, 36, 38, 38, 41, 40, 41}

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

    2

    Returns: 0

  67. {0, 1, 2, 2, 2, 3, 6, 6, 7, 7, 8, 10, 10, 11, 13, 14, 14, 15, 18, 17, 18, 19, 21, 21, 24}

    {13, 6, 9, 18, 20, 1, 17, 5, 8, 14, 4, 12, 15, 16, 24, 0, 21, 23, 22, 2, 11, 19, 25}

    46

    Returns: 3

  68. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {14, 21, 10}

    10

    Returns: 3

  69. {0, 0, 2, 1, 2, 4, 4, 6, 6, 7, 8, 9, 10, 13, 14, 15, 16, 17, 16, 17, 19, 21, 22}

    {10, 8, 9, 4, 22, 20, 13, 21, 15, 16, 7}

    35

    Returns: 11

  70. {0, 1, 1, 2, 4, 5, 6, 5, 6, 7, 9, 10, 10, 11, 13, 14, 15, 17, 18, 19, 18, 19, 20, 22, 24, 25, 26, 27, 27, 29, 30, 31, 32}

    {17, 4, 2, 16, 19, 26, 27, 31, 13, 33, 15, 28, 25, 30, 20, 1, 7, 22, 23, 3, 12, 6, 24, 9, 21, 10, 14, 8, 5, 32, 18}

    2

    Returns: 3

  71. {0, 0, 1, 0, 3, 3, 3, 3, 3, 1, 0, 3, 1, 1, 3, 0, 3, 3, 3, 2, 1, 3, 3, 1, 0, 0, 1, 1, 3, 1, 3, 0, 1, 2, 0, 1, 1, 3, 0, 3, 2}

    {31, 12, 22, 28, 36, 2, 11, 25, 34, 6, 9, 23, 3, 17, 1, 13, 21, 38, 33, 7, 4, 5, 15, 19, 40, 27, 35, 37, 14, 20, 39, 16}

    50

    Returns: 10

  72. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {2, 9, 0, 23, 22, 16, 19, 11, 14, 27, 20, 13, 25, 28, 3, 21, 5, 17, 6, 24, 10, 1, 7, 8}

    9

    Returns: 5

  73. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {6, 13, 36, 11, 4, 27, 25, 10, 34, 19, 26, 23, 28, 14, 17, 2, 20, 9, 24, 21, 3, 16, 5, 18, 30, 35, 12, 7, 31, 22, 33, 29, 32, 8, 15, 1, 0}

    2

    Returns: 0

  74. {0, 0, 0, 0, 3, 0, 0, 0, 3, 3, 2, 3, 2, 2, 0, 2, 1, 3, 1, 0, 3, 2, 0, 1, 1, 0, 1, 2, 3, 1, 0, 2, 0, 3, 0, 1, 0, 2}

    {6, 27, 17, 26, 3, 34, 12, 18, 13, 23, 8, 30, 2, 9, 35, 29}

    14

    Returns: 16

  75. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {16, 0, 3, 15, 10, 13, 4, 12, 5, 8, 7, 17, 9}

    5

    Returns: 5

  76. {0, 1, 0, 1, 2, 4, 4, 7, 7, 7, 10, 11, 11, 13, 14, 15, 15, 17, 16, 19, 18, 20, 21, 21, 22, 24, 26, 25, 26, 27, 30, 31, 31, 33}

    {3, 10, 1, 19, 26, 31, 24, 12, 20, 2, 23, 6, 17, 4, 0, 8, 34, 9, 7, 33, 22, 27, 21, 15, 30, 29}

    7

    Returns: 9

  77. {0, 0, 0, 0, 0, 0, 0, 0}

    {1, 0, 5, 3, 2}

    4

    Returns: 4

  78. {0, 1, 2, 2, 3, 5, 5, 5, 8, 8, 9}

    {7, 10, 4, 9, 5, 8, 2, 11, 0}

    5

    Returns: 3

  79. {0, 0, 0}

    {0}

    2

    Returns: 1

  80. {0, 1, 2, 2, 2, 3, 3}

    {3, 1, 2, 5, 4}

    10

    Returns: 3

  81. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {17, 19, 12, 21, 15, 24, 7, 23, 11, 2, 5, 20, 16, 0, 18, 6, 1, 13, 9, 8}

    4

    Returns: 4

  82. {0, 0, 2, 3, 4, 4, 5, 7, 7, 9, 10, 11, 12, 12, 13, 15, 16, 16, 17, 17, 20, 20, 22, 21, 24, 25}

    {9, 1, 22, 3, 7, 17, 18, 16, 0, 11, 2, 25, 4, 12, 26}

    20

    Returns: 12

  83. {0, 1, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 12, 11, 13, 15, 14, 17, 16, 18, 19, 19, 22, 21, 22, 24, 24, 26, 28, 28, 30, 31, 30, 31, 34, 34, 36, 36, 36}

    {1, 34, 15, 3, 26, 8, 37, 6, 7, 11, 10, 2, 16, 32, 39, 18, 28, 17, 35, 19, 21, 27, 33, 23, 22, 30}

    10

    Returns: 14

  84. {0, 1, 2, 1, 2, 3, 4, 5, 6, 7, 10, 11, 11, 12, 14, 15, 16, 16, 16, 19, 18, 21, 21, 23, 24, 25, 24, 27, 28, 28, 28, 31, 31, 31, 32, 35, 34, 36, 36, 39, 39, 40}

    {13, 23, 16, 19, 29, 30, 3, 9, 8, 4, 20, 32, 36, 42, 12, 21, 40, 7, 14, 10, 39, 11, 37, 22, 25, 26, 18, 2, 5, 0, 34, 28, 1, 15, 17, 31, 27, 41, 33, 38}

    33

    Returns: 3

  85. {0, 1, 2, 2, 3, 1, 1, 1, 0, 3, 2, 3, 2, 0, 3, 3, 2, 1, 3, 2, 3, 1, 1, 1, 0, 3, 2, 1, 3, 0, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 0, 1, 2, 1, 0, 2, 0, 3, 0}

    {3, 17, 24, 16, 31, 32, 8, 23, 13, 48, 1, 41, 26, 35, 14, 7}

    8

    Returns: 16

  86. {0, 0, 1, 2, 3, 3, 5, 7, 7, 8, 9, 11, 12, 13, 13, 13, 15, 15, 18, 17, 18, 20, 21, 23, 23, 24, 26, 26, 26, 28}

    {17, 7, 11, 30, 3, 29, 6, 12, 26, 9, 19, 0, 24, 5, 13, 14, 4, 10, 1, 22, 8, 2, 28, 15, 27, 23, 25, 21, 18, 16}

    4

    Returns: 1

  87. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {38, 7, 28, 16, 24, 1, 37, 10, 40, 23, 13, 9, 11, 19, 34, 25, 35, 12, 3, 17, 4, 31, 22, 26, 14, 29}

    40

    Returns: 15

  88. {0, 0, 0, 1, 3, 1, 1, 3, 2, 0, 0, 2, 1, 3, 3, 1, 3, 1, 1, 0, 0}

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

    29

    Returns: 0

  89. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {8, 2, 14, 16, 12, 5, 11, 1, 10, 9, 17, 7, 13, 6, 3, 0}

    6

    Returns: 2

  90. {0}

    {0, 1}

    22

    Returns: 0

  91. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {7, 19, 24, 10, 12, 3, 11, 26, 5, 6, 0, 25, 21, 16, 14, 2, 17, 18, 20, 13}

    10

    Returns: 7

  92. {0, 1, 0, 2, 1, 1}

    {3, 6}

    3

    Returns: 2

  93. {0, 0, 0, 0, 0, 0, 0, 0, 0}

    {6, 3, 2, 9, 7}

    29

    Returns: 5

  94. {0, 0, 0, 0, 0, 0}

    {1, 0, 5, 4, 3}

    10

    Returns: 2

  95. {0, 0, 0, 1, 4, 4, 5, 7, 6, 7, 10, 11, 11, 13, 12, 13, 14, 17, 16, 17, 20, 21, 21, 21, 24, 25, 25, 26, 27, 27, 29, 29, 32, 33, 34, 34, 35, 36, 37, 38, 38, 41, 42, 41}

    {37, 31, 42, 39, 13, 38, 7, 41, 27, 17, 21, 11, 20, 24, 14, 26, 4, 25}

    40

    Returns: 18

  96. {0, 0, 1, 2, 1, 1, 3, 0, 2, 3, 0, 1, 0, 1, 1, 0, 2, 3, 3, 0, 0, 0, 1, 3, 0, 2, 3, 0, 1, 2, 3, 3, 2, 3, 2, 2, 1}

    {6, 9, 32, 33, 23, 8, 30}

    1

    Returns: 4

  97. {0, 0, 0, 3, 3, 0, 1, 2, 3, 1, 1, 0, 2, 1, 2, 0, 3, 1, 1, 2, 0, 1, 0, 2}

    {3, 11, 10, 7, 9, 23, 1, 0, 24, 17, 22, 16, 14, 6, 12, 21, 8, 2, 4}

    50

    Returns: 6

  98. {0, 1, 0, 3, 3, 3, 2, 3, 2, 3, 3, 0, 2, 1, 3, 0, 2, 1, 2, 2, 2, 1, 2, 1, 1, 0, 2, 2}

    {21, 25, 11, 8, 19, 27, 23, 28, 4, 12, 3, 14}

    1

    Returns: 4

  99. {0, 0, 1, 2, 3, 1}

    {1, 0, 4, 3, 6, 2, 5}

    50

    Returns: 0

  100. {0, 0, 0, 0, 0}

    {3, 0, 1, 4, 5, 2}

    4

    Returns: 0

  101. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {21, 7, 1, 12, 28, 0, 8, 37, 6, 38, 22, 39, 20, 11}

    48

    Returns: 14

  102. {0, 0, 2, 2, 2, 4, 6, 6, 6}

    {8, 4, 7, 6, 9, 1, 3}

    9

    Returns: 3

  103. {0, 0, 2, 0, 1, 3, 3, 1, 1, 2, 0, 1}

    {5, 10, 11, 4, 7, 6, 3, 2, 1, 9, 12}

    1

    Returns: 2

  104. {0, 0, 0, 3, 3, 4, 6, 5, 8, 8, 10, 10}

    {3, 11, 6, 10, 0, 7, 12, 5, 1, 2}

    8

    Returns: 3

  105. {0, 0, 2, 1, 0, 3, 3, 1, 3, 0, 0, 2, 1, 2, 1, 0, 1, 3, 3, 0, 0, 2, 1, 3, 2}

    {5, 25, 6, 14, 24, 11, 17, 15, 0, 3, 1, 18, 8, 12, 7, 10, 13, 23, 20}

    6

    Returns: 7

  106. {0, 0, 2, 1, 1, 3, 2, 0, 0, 3, 1, 0, 3, 2, 2, 2, 2, 0, 2, 1, 1, 0, 1, 0, 2, 1, 3, 0, 0, 3, 3, 2, 1, 0, 2, 2, 1, 2, 0, 1}

    {37, 34, 9, 38, 20, 5, 36, 21, 15, 17, 1, 30, 14, 39, 0, 4, 3, 33, 32, 16, 19, 35, 31, 29, 22, 13, 12, 7, 27, 28, 23, 8, 18, 11, 2, 25}

    7

    Returns: 5

  107. {0,0,0}

    {1,2}

    1

    Returns: 1

    We can only save one of the two tokens, because we only have a single turn and we cannot push both of them into the same node.

  108. {0, 0, 0, 0, 0 }

    {0, 1, 2 }

    2

    Returns: 2

  109. {0, 0, 0, 0, 0 }

    {1, 2, 3 }

    2

    Returns: 2

  110. {0, 1, 1, 1, 3 }

    {3, 4, 5 }

    2

    Returns: 2

  111. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {0, 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 }

    10

    Returns: 10

  112. {0, 0, 0, 0, 0, 0, 0, 0 }

    {1, 2, 3, 4 }

    2

    Returns: 2

  113. {0, 1, 0, 3, 0, 5, 6, 5, 8 }

    {0, 1, 2, 3, 4 }

    4

    Returns: 4

  114. {0 }

    {0 }

    2

    Returns: 1

  115. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {1, 2, 3, 4, 5, 6 }

    2

    Returns: 2

  116. {0, 1, 2, 3, 4, 3, 6, 3 }

    {3, 4, 5, 6, 7 }

    2

    Returns: 2

  117. {0, 0, 0, 0, 0, 0 }

    {1, 2, 3 }

    2

    Returns: 2

  118. {0, 0, 0, 0, 4 }

    {0, 1, 2 }

    2

    Returns: 2

  119. {0, 1, 1, 3, 3, 5, 6 }

    {0, 1, 2, 3 }

    4

    Returns: 4

  120. {0, 0, 0, 0, 0, 0 }

    {4, 5, 6 }

    2

    Returns: 2

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: