**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.**