Statistics

Problem Statement for "TheAnimalProgrammingCompetitions"

Problem Statement

Cat Taro and rabbit Hanako are running the animal programming competitions in a forest. John and Brus are invited as judges. Each team that takes part in the competitions consists of exactly four members. Each team member is either a cat or a rabbit. You are given a int[] rabbits. The number of teams that take part in the competitions is equal to the number of elements in rabbits. For each i, team number i (0-based index) consists of rabbits[i] rabbits and 4-rabbits[i] cats.

According to the best traditions of the animal programming competitions, each rabbit brings one carrot at the opening ceremony and presents it to some participant (either a cat or a rabbit) from a different team. The rabbits always coordinate their choices in order to make sure that no participant receives more than one carrot as a present. It seems this task is not that easy for the rabbits, so they asked the judges (John and Brus) to help them. Now John and Brus are thinking of a carrot distribution plan. All the carrots are considered pairwise distinct. Hence, two distribution plans are considered distinct if and only if there is at least one participant that receives a different present (i.e., either a different carrot in each plan, or a carrot in one plan and no carrot in the other). Return the number of different distribution plans, modulo 1,234,567,891.

Definition

Class:
TheAnimalProgrammingCompetitions
Method:
find
Parameters:
int[]
Returns:
int
Method signature:
int find(int[] rabbits)
(be sure your method is public)

Constraints

  • rabbits will contain between 1 and 47 elements, inclusive.
  • Each element of rabbits will be between 0 and 4, inclusive.

Examples

  1. {0, 1, 0}

    Returns: 8

    There are eight options for the only rabbit in the competitions.

  2. {4}

    Returns: 0

    Rabbits can't present carrots to their teammates.

  3. {1, 1, 0}

    Returns: 60

    If the first rabbit presents their carrot to somebody from the second rabbit's team then there are eight options for the second rabbit, if not - only seven. Thus the total number of different plans is 4*8 + 4*7 = 60.

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

    Returns: 644027397

  5. {4, 0, 1, 4}

    Returns: 289859328

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

    Returns: 32187477

  7. {4, 3, 2, 3, 4, 3}

    Returns: 15372184

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

    Returns: 1192251892

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

    Returns: 575188766

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

    Returns: 553764147

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

    Returns: 873216576

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

    Returns: 307990481

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

    Returns: 247172110

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

    Returns: 831727895

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

    Returns: 87472503

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

    Returns: 92690001

  17. {0, 0, 1, 4, 1, 1}

    Returns: 473381184

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

    Returns: 992841155

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

    Returns: 943518054

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

    Returns: 279276329

  21. {4}

    Returns: 0

  22. {4}

    Returns: 0

  23. {2}

    Returns: 0

  24. {2}

    Returns: 0

  25. {2}

    Returns: 0

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

    Returns: 951180662

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

    Returns: 323306206

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

    Returns: 753100489

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

    Returns: 330799340

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

    Returns: 968876250

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

    Returns: 1216096713

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

    Returns: 155535860

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

    Returns: 505657780

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

    Returns: 62625491

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

    Returns: 526905487

  36. {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}

    Returns: 1

  37. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 102625890

  38. {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

    Returns: 739243282

  39. {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

    Returns: 351519830

  40. {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

    Returns: 855881796

  41. {3, 4}

    Returns: 576

  42. {3, 4}

    Returns: 576

  43. {3, 4}

    Returns: 576

  44. {3, 4}

    Returns: 576

  45. {2, 3, 2, 2, 3, 3, 3, 2, 3, 2, 2, 2, 2, 2, 3, 2, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3, 3, 2, 3}

    Returns: 1068933776

  46. {3, 3, 2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 3, 2, 2, 3, 3, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 3, 2}

    Returns: 626966760

  47. {3, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 3, 2, 3, 2, 2, 3, 2, 2, 2, 2, 3, 2}

    Returns: 903857730

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: