**Author:** Praveen Dhinwa

**Tester:** Istvan Nagy

**Editorialist:** Misha Chorniy

# Difficulty:

Cakewalk

# Pre-Requisites:

None

# Problem Statement

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?

# Explanation

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.

# Subtask 3

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.

# Solution:

Setter's solution can be found here

Tester's solution can be found here

**Please feel free to post comments if anything is not clear to you.**