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