Hi. I have encountered this problem recently and didn't know how to approach it.
We want to construct compounds with these properties:
Chas 4 links and can bond with eitherC,HorIHcan bond withConly through 1 linkIcan bond withConly through 2 links- there is no atom with one or more free links
For example, H-C=C is not a compound because the middle C needs another link and the right one 2 more.
Two compounds are different if the numbers of C, H or I differ.
Now we define the mass of a compound as 5 * no. of C + 3 * no. of I + no. of H.
Task
Given 30 <= N <= 100000, find how many compounds with mass N there are with at least one C, I and H.
Example:
Input: N = 40
Output: 3
Explanation
These are the only possible compounds with mass 40:










First of all, notice that the picture is a little misleading; it’s always enough to check configurations where the graph induced by the C-molecules is a chain. It’s a little tough to formally prove, but the rough idea is that this setup maximizes both the number of I-molecules that you can attach and the number of H-molecules that you can further attach (for a fixed number of I).
Another important observation is that there should be an even number of H-molecules (the sum of degrees in the graph is even).
Then, let’s fix the number $$$C$$$ of C ($$$N \geq 30$$$ implies $$$C \geq 2$$$) molecules. For each fixed $$$C$$$, you have two cases:
Thank you!