There are $C$ cats and $D$ dogs, and $L$ legs touching the ground. Some of the cats can ride on dogs, but every dog can't have more than 2 cats on his back. Can this be true?
Let's make some obvious observations:
- Every cat has 4 legs.
- Every dog has 4 legs.
If we have $X$ cats and $Y$ dogs staying on the ground then, the number of legs in the barn equal $4 * (X+Y)$. Therefore if $L$ not divisible by 4, the answer is "no".
Subtask 1 and 2
Constraints are chosen in such way that solutions with complexity $O(D+C)$ per test case can pass.
Iterate over possible numbers of the cats on Chef's dogs back $G$($G$ must be in the range between $0$ and $2*D$ due to the condition of the dog and 2 cats on his back, and not more than the total number of cats). Hence in the barn $4*(C-G+D)$ legs on the ground, if $4*(C-G+D) = L$ for some $G$, then the answer is "yes", and "no" otherwise.
There is possible to solve problem with $O(1)$ solution per test case. Let $G$ number of the cats on the backs of the dogs, $0 ≤ G ≤ min(C,2*D)$
$4*(C-G)+4*D = L $, there are $C-G$ cats on the ground, therefore total number of legs = $4*(C-G)$+$4*D$
$C-G+D = L/4 $, divide both parts of the equation by $4$
$C+D-L/4 = G $, add $G-L/4$ to both parts of the equation
if $G$ will be in the range between $0$ and $2*D$ answer is "yes", and "no" otherwise.
The overall time complexity of this approach is $O(1)$ per test case.
Please feel free to post comments if anything is not clear to you.