JOIN
Get Time

   Problem Statement  

 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

0)
    
{0, 1, 2, 3, 4}
Returns: 2
There are two possible configurations: all animals are rabbits or all animals are cats.
1)
    
{5, 8}
Returns: 0
There are only two animals. These animals are definitely lying.
2)
    
{0, 0, 0, 0, 0, 0}
Returns: 0
3)
    
{1, 0, 2, 0, 1}
Returns: 8
4)
    
{1, 0, 1}
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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 511 Round 1 - Division I, Level One
       Single Round Match 511 Round 1 - Division II, Level Two