DecreasingPopulation
2022 HF Final · 2022-03-16 · by misof
Problem Statement
Once there was a planet with S inhabitants.
The planet then faced N bad years in a row. Each year exactly one bad thing happened: either the planet got hit by a small asteroid, or the planet got visited by the space dragon.
Preserved historical records tell us the following:
- The space dragon always ate exactly one inhabitant.
- An asteroid hit always killed exactly one half of the population.
- During the N years nobody was born and nobody died for another reason.
Given all this information we would like to determine the current population of this planet. However, the answer to this question is not necessarily unique. Count all options that are consistent with all the above information, and return that count.
Notes
- One half of zero is zero. Hence, it is possible that after everyone died there were some additional asteroid hits.
Constraints
- S will be between 1 and 5,000, inclusive.
- N will be between 1 and 5,000, inclusive.
24 1 Returns: 2
The original population consisted of S = 24 people. There was N = 1 bad event. The answer is 2 because now there are two options: If there was an asteroid hit, the current population is 12. If there was a dragon visit, the current population is 23.
17 1 Returns: 1
As the original population was odd, we can deduce that the only bad event must have been a dragon visit and thus the current population must be 16.
2 2 Returns: 1
Regardless of what the first event was, it killed one person. The second event must have been a dragon visit that killed the other person. Thus, there is only one valid option: the current population is 0.
30 3 Returns: 4
1 5000 Returns: 1
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DecreasingPopulation with a public method int count(int S, int N) · 90 test cases · 2 s / 256 MB per case