DinkyFish
SRM 180 · 2004-01-22 · by Eeyore
Problem Statement
The dinky is a small fish that breeds monogamously and regularly. Within days of its birth, the male of the species seeks out a mate and bonds with her for life, never dallying with another. At the end of every month, the couple issues exactly two offspring, of which one is a boy and the other a girl. Each of these, in turn, goes off on its amorous quest. Inbreeding is not uncommon in the confines of a fish tank, so a pair of cousins or even siblings may end up mating. If there are more females than males, the excess number who cannot secure a mate will not give birth in that month.
Despite their diminutive dimensions and peaceful nature, a population of dinkies must not be allowed to multiply ad infinitum. Experts recommend that one allot at least half a liter of water per dinky fish. Anything less than that, and the tank is said to be crowded. The solution is either to buy a larger tank or to catch some dinkies for breakfast.
Given the volume of a tank in liters, the number of male dinkies currently inhabiting the tank, and the number of females present, you are to calculate the number of months that can elapse before the tank becomes crowded. Bear in mind that all couples reproduce simultaneously at the end of every month. If the input values are such that the tank is already crowded, the correct answer is 0. If the tank will become crowded at the end of the first month, the answer is 1.
Notes
- Disregard the effects of mortality. Assume that all dinkies, young and old, live perpetually.
Constraints
- tankVolume is between 1 and 1000000 (one million), inclusive
- maleNum is between 1 and 1000, inclusive
- femaleNum is between 1 and 1000, inclusive
10 4 6 Returns: 2
Four couples form initially. At the end of the first month, four male and four female dinkies are born. There are now 18 dinky fish in total and eight couples. At the end of the second month, eight dinkies of each sex are born, for a total of 34, which does not allow for half a liter each in a ten-liter tank. Thus, it has taken two months to reach a crowded state.
100 4 6 Returns: 5
At the end of the fourth month, there are 130 dinky fish. At the end of the fifth, there are 258.
5 6 4 Returns: 1
A five-liter tank is just large enough for ten dinkies, but it becomes crowded at the end of the first month.
4 6 4 Returns: 0
This four-liter tank is already crowded with ten dinkies.
1000000 3 2 Returns: 19
Submissions are judged against all 124 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DinkyFish with a public method int monthsUntilCrowded(int tankVolume, int maleNum, int femaleNum) · 124 test cases · 2 s / 256 MB per case