Cactus
SRM 123 · 2002-12-10 · by axchma
Problem Statement
John has a cactus. Sadly, John has only one cactus, and that cactus is lonely. Recently, however, John won $50,000, so he decided to buy some friends for his cactus. Now, everybody knows that the best cactuses in the world can be found at TopCactus.com. TopCactus.com has thousands and thousands of cactuses, and new ones arrive every day. They have so many, that they do not even have time to put prices on all of them. We are not interested in cactuses that do not yet have prices. Now, there are two kinds of priced cactuses. Some of them do not have flowers, and are by themselves gray or green. John does not want any of those. There are also cactuses with flowers. Cactuses with blue flowers are sold for prices ranging from $1,200 to $1,499 inclusive, those with yellow flowers go for between $1,500 and $2,199 inclusive, and those with red flowers cost between $2,200 and $2,999 inclusive. Also, there is a very small number of very, very rare cactuses, which have flowers that are red with a white center. These cactuses cost $3,000 or more and they are so unique and incomparable to each other that no two of them are ever sold for the same price.
Your task is, given the amount of money John spent buying cactuses from TopCactus.com and the number of very rare red-and-white cactuses available at TopCactus, return the number of different combinations of colors of cactuses there are that John could have bought.
For example, if John spent $3,500 and there was at least one very rare cactus: he could have bought one very rare red and white cactus for $3,500; or he could have bought one red cactus and one blue cactus; or two yellow cactuses; or a more expensive yellow and a blue. Return 4.
Notes
- Though every cactus is unique and special, and even has its own name, for our purpose of counting color combinations, we consider different cactuses with the same color of flowers to be identical (so a blue cactus for $1,200 and a red cactus for $2,500 is not a different combination from a blue cactus for $1,400 and a red cactus for $2,300).
- The more expensive a cactus, the more difficult it is to grow or find, of course, so they are less common, but John does not have enough money to exhaust the supply of TopCactus.com of any color of cactus, except the very rare ones with red-and-white flowers, of which TopCactus can have up to five exemplars.
- We do not know the actual prices of the individual cactuses because they change nearly every week, so we assume that, if John wanted to, he could buy a cactus with a given color of flowers for any price within that range. (In particular, he might blow all $50,000 on a single cactus!)
- As an exception to that, though, we know that the very rare cactuses with red-and-white flowers have very different personalities (for instance, one of them has a tendency to snap at people) so no two of them are ever the same price.
Constraints
- moneyGone is between 1200 and 50000 inclusive
- numRare is between 0 and 5 inclusive
3500 4 Returns: 4
6000 3 Returns: 18
Note that John couldn't have bought two very rare red-and-white cactuses as they should be different in price
50000 5 Returns: 21233
2002 5 Returns: 1
20000 1 Returns: 574
3500 0 Returns: 3
Observe that here, as opposed to in example 0, there are no very rare cactuses at TopCactus.com, so John could not have bought any of them.
49012 0 Returns: 3332
Ten random test cases
Submissions are judged against all 44 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Cactus with a public method int colorCombo(int moneyGone, int numRare) · 44 test cases · 2 s / 256 MB per case