A necklace maker has currently $b$ blue rubies, $g$ green rubies, $r$ red rubies and $y$ yellow rubies. He has to arrange the rubies next to each other in a straight line to make the necklace. But, there are a couple of rules to be followed while making this necklace:
- A blue ruby should be followed by either a blue ruby or a red ruby.
- A green ruby should be followed by either a green ruby or a yellow ruby.
- A red ruby should be followed by either a green ruby or a yellow ruby.
- A yellow ruby should be followed by either a blue ruby or a red ruby.
Can you tell what the maximum possible length of the necklace that the necklace maker can make is? The length of a necklace is the number of rubies in it.
Input Format:
- The first line contains an integer representing $b$.
- The second line contains an integer representing $g$.
- The third line contains an integer representing $r$.
- The fourth line contains an integer representing $y$.
Constraints:
- $0 \leq b, g, r, y \leq 3000$.
- At least one of $b, g, r, y$ is greater than 0.
Hint: Contrary to what the tight bounds on the inputs suggest, the answer can be found in $O(1)$. One only needs to distinguish the following cases, each allowing a straightforward answer in terms of $r,g,b,y$:
Remark: My research find traces of the problem statement only dated almost a month ago, but seemingly not the original problem statement. Given that the answer is almost a no-brainer once you stop viewing it as a programming problem with hefty recursion, I assume that after this time, the contest is over / cannot be spoiled by a full solution. So here is the full answer:
If $r=y=0$, the necklace must be monochromatic because now green can only be followed by green and blue only by blue. Hence the answer is $$\max\{b,g\}\qquad \text{if }r=y=0.$$
If $r>0$ and/or $y>0$, observe that between any two red beans, the must be a yellow bean, and between any two yellow beans, there must be a red bean (and possibly some blue and/or green beans). Hence the number of red beans and yellow beans in the final necklace cannot differ by more than one. On the other hand, we can use all available green beans (after any red or before any yellow bean - at least one must exist) and all available blue beans (after any yellow or before any red bean). We arrive at the necklace length $$ g+b+r+y\qquad \text{if }r=y>0$$ and $$ g+b+2\min\{r,y\}+1\qquad \text{if }r\ne y.$$