Animals | Topcoder Archive

Problem Statement

A farmer has a number of animals on his farm. He has several different types of animals. Given the number of total heads that are present at the farm, the number of total legs, and the number of legs of each type of animal, return the number of different configurations the farmer could possibly have. A configuration is how many of each type of animal the farmer has. For two configurations to be different, the number of at least one type of animal needs to be different.

For example, if the farmer raises sheep, monkeys, butterflies, and cows, the four types of animals would have 4, 2, 6, and 4 legs respectively. If legs is 4 and heads is 1, the farmer has two possible configurations, 1 sheep, or 1 cow.

Create a class Animals that contains the method numWays, which takes three arguments:
heads: how many heads of animals are present on the farm
legs: how many legs of animals are present on the farm
types: a int[] whose elements tell how many legs each type of animal has.
The method should return an int, which should be how many possible different configurations of animals there could be.

Definition

Class:: Animals
Method:: numWays
Parameters:: int, int, int[]
Returns:: int
Method signature:: int numWays(int heads, int legs, int[] types)
(be sure your method is public)

Notes

All animals on the farm have exactly one head.
There are no animals on the farm with missing limbs.

Constraints

heads is between 1 and 200 inclusive
legs is between 1 and 2000 inclusive
types has between 1 and 5 elements inclusive
Each element of types is between 1 and 15 inclusive

Examples

```
1
```
```
4
```
```
{4,2,6,4}
```
```
Returns: 2
```
This is the example stated above.
```
100
```
```
400
```
```
{4,4}
```
```
Returns: 101
```
If the farmer has sheep and cows, there are 101 different possibilities. The configurations are: (0 cows, 100 sheep), (1 cow, 99 sheep), (2 cows, 98 sheep), ..., (99 cows, 1 sheep), (100 cows, 0 sheep).
```
100
```
```
300
```
```
{1,2,3,4,5}
```
```
Returns: 29920
```
```
59
```
```
230
```
```
{2,15,11,1,8}
```
```
Returns: 645
```

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.