Statistics

Problem Statement for "Zoo"

Problem Statement

There are N animals numbered 0 to N-1 in a zoo. Each animal is a rabbit or a cat. Their heights are pairwise distinct.

Fox Jiro can't distinguish between rabbits and cats, so he asked the following question to each animal: "How many animals of the same kind as you are taller than you?" Each rabbit tells the number of rabbits taller than him, and each cat tells the number of cats taller than her. The differences of heights are slight, so Fox Jiro can't tell which animals are taller than other animals. However, each animal is able to determine which animals are taller that him and which ones are shorter.

The answer given by the i-th animal is answers[i]. Given these numbers, return the number of configurations resulting in exactly those numbers, assuming everyone tells the truth. Two configurations are different if there exists an i such that the i-th animal is a rabbit in one configuration and cat in the other configuration.

Definition

Class:
Zoo
Method:
theCount
Parameters:
int[]
Returns:
long
Method signature:
long theCount(int[] answers)
(be sure your method is public)

Constraints

  • answers will contain between 1 and 40 elements, inclusive.
  • Each element of answers will be between 0 and 40, inclusive.

Examples

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

    Returns: 2

    There are two possible configurations: all animals are rabbits or all animals are cats.

  2. {5, 8}

    Returns: 0

    There are only two animals. These animals are definitely lying.

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

    Returns: 0

  4. {1, 0, 2, 0, 1}

    Returns: 8

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

    Returns: 8

  6. {1, 0, 0, 1}

    Returns: 4

  7. {1, 1}

    Returns: 0

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

    Returns: 1048576

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

    Returns: 65536

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

    Returns: 131072

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

    Returns: 262144

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

    Returns: 524288

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

    Returns: 1048576

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

    Returns: 1048576

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

    Returns: 65536

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

    Returns: 131072

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

    Returns: 262144

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

    Returns: 524288

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

    Returns: 1048576

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

    Returns: 2

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

    Returns: 4

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

    Returns: 8

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

    Returns: 16

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

    Returns: 32

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

    Returns: 2

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

    Returns: 4

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

    Returns: 8

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

    Returns: 16

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

    Returns: 32

  30. {0}

    Returns: 2

  31. {0, 1}

    Returns: 2

  32. {2, 1, 0}

    Returns: 2

  33. {1, 3, 2, 0}

    Returns: 2

  34. {0}

    Returns: 2

  35. {0, 0}

    Returns: 2

  36. {0, 0, 1}

    Returns: 4

  37. {0, 0, 1, 2}

    Returns: 4

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

    Returns: 4

  39. {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, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39}

    Returns: 2

  40. {25, 39, 0, 34, 21, 14, 20, 5, 27, 16, 31, 8, 35, 20, 8, 25, 33, 35, 38, 2, 18, 20, 27, 11, 28, 18, 32, 20, 3, 23, 39, 29, 16, 18, 28, 26, 33, 5, 32, 4}

    Returns: 0

  41. {9, 31, 21, 10, 12, 26, 11, 15, 23, 21, 1, 19, 22, 39, 21, 2, 6, 27, 29, 29, 12, 1, 10, 11, 17, 16, 2, 1, 40, 11, 22, 14, 34, 17, 13, 37, 18, 15, 9, 26}

    Returns: 0

  42. {0, 19, 0, 26, 8, 10, 32, 40, 16, 20, 22, 3, 32, 5, 38, 27, 24, 13, 34, 6, 30, 40, 5, 7, 39, 19, 32, 38, 8, 17, 1, 34, 25, 40, 35, 16, 27, 29, 18, 14}

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

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

    Returns: 1048576

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

    Returns: 0

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

    Returns: 0

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

    Returns: 0

  52. {1, 0, 1}

    Returns: 0

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

    Returns: 2

  54. {0, 0 }

    Returns: 2

  55. {0, 1, 1, 0 }

    Returns: 4

  56. {40, 40 }

    Returns: 0

  57. {0, 0, 1, 1 }

    Returns: 4

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

    Returns: 16

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

    Returns: 1048576

  60. {1, 1, 0, 0 }

    Returns: 4

  61. {0, 1, 0, 1 }

    Returns: 4

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

    Returns: 8

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

    Returns: 8

  64. {0 }

    Returns: 2

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

    Returns: 16

  66. {0, 0, 1, 2, 2 }

    Returns: 0

  67. {1, 0, 0, 1 }

    Returns: 4

  68. {0, 0, 2, 2 }

    Returns: 0

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

    Returns: 524288

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

    Returns: 2

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

    Returns: 1048576

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

    Returns: 0

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

    Returns: 8

  74. {0, 0, 0 }

    Returns: 0

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

    Returns: 32

  76. {0, 0, 1, 1, 2, 2 }

    Returns: 8

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

    Returns: 4

  78. {12, 1, 2, 3, 4, 3, 12, 12, 2, 3, 2, 2, 3, 2, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1 }

    Returns: 0

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

    Returns: 2

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

    Returns: 64

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

    Returns: 64

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

    Returns: 16

  83. {1, 0, 2, 0, 1 }

    Returns: 8

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

    Returns: 1048576

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

    Returns: 8

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

    Returns: 4

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

    Returns: 0

  88. {1 }

    Returns: 0

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

    Returns: 0

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

    Returns: 16

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

    Returns: 0

  92. {0, 1, 5 }

    Returns: 0

  93. {0, 0, 1 }

    Returns: 4

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

    Returns: 8

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

    Returns: 32

  96. {0, 2 }

    Returns: 0

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

    Returns: 1048576

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

    Returns: 8

  99. {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

    Returns: 64

  100. {0, 0, 2, 2, 1, 1 }

    Returns: 8

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

    Returns: 131072

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

    Returns: 4

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

    Returns: 0

  104. {1, 1, 1 }

    Returns: 0

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

    Returns: 8

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

    Returns: 16

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

    Returns: 512

  108. {0, 1, 2, 1, 2 }

    Returns: 0

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

    Returns: 16

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

    Returns: 0

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

    Returns: 8

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

    Returns: 32

  113. {1, 1, 2, 2 }

    Returns: 0

  114. {40 }

    Returns: 0

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

    Returns: 4

  116. {1, 0, 2, 1, 1 }

    Returns: 0

  117. {1, 2 }

    Returns: 0

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

    Returns: 64

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

    Returns: 16

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

    Returns: 32

  121. {0, 1, 0 }

    Returns: 4

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

    Returns: 128

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

    Returns: 0

  124. {0, 1, 0, 1, 3 }

    Returns: 0

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

    Returns: 0

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

    Returns: 32

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

    Returns: 0

  128. {1, 0, 0, 1, 2, 2 }

    Returns: 8

  129. {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 12 }

    Returns: 0

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

    Returns: 0

  131. {0, 0, 1, 2, 5 }

    Returns: 0

  132. {0, 0, 1, 2 }

    Returns: 4

  133. {1, 1 }

    Returns: 0

  134. {1, 0, 2, 0, 1, 2 }

    Returns: 8

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

    Returns: 8

  136. {1, 0, 1, 0 }

    Returns: 4

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

    Returns: 16

  138. {0, 1, 2, 0, 1, 2, 4 }

    Returns: 0

  139. {0, 0, 1, 2, 2, 2 }

    Returns: 0

  140. {0, 0, 0, 1, 1, 1, 3, 3 }

    Returns: 0

  141. {0, 1, 2, 2, 0, 1 }

    Returns: 8

  142. {7, 6, 5 }

    Returns: 0

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

    Returns: 524288

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

    Returns: 16

  145. {0, 1, 3 }

    Returns: 0

  146. {3 }

    Returns: 0

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

    Returns: 4

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: