Animals
SRM 115 · 2002-09-30 · by schveiguy
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
The method should return an
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
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
200
200
{1,1,1,1,1}
Returns: 70058751
Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Animals with a public method int numWays(int heads, int legs, vector<int> types) · 30 test cases · 2 s / 256 MB per case