Shizuku Hoshikawa and Farm Legs

Core Idea

Let:

• $c$ = number of chickens
• $w$ = number of cows

A chicken has $2$ legs and a cow has $4$ legs, so every valid configuration must satisfy:

$$2c + 4w = n$$

where $c \ge 0$ and $w \ge 0$ are integers.

We are counting how many different pairs $(c, w)$ work.

Odd $n$ Is Impossible

The expression $2c+4w$ is always even because both terms are even. So if $n$ is odd, there is no way to make exactly $n$ legs. Answer: $0$.

That handles cases like $n=3$. No need to overthink it. Odd legs on a chicken/cow farm means someone is lying or the farm is cursed.

Even $n$

Now suppose $n$ is even. Divide the equation by $2$:

$$c + 2w = \frac n2$$

Let:

$$m = \frac n2$$

Then:

$$c + 2w = m$$

Here is the key move: choose the number of cows $w$. Then the number of chickens is forced:

$$c = m - 2w$$

So every valid cow count gives exactly one valid configuration, as long as $c \ge 0$.

That means:

$$m - 2w \ge 0$$ $$2w \le m$$ $$w \le \left\lfloor \frac m2 \right\rfloor$$

Since $w$ can also be $0$, the possible cow counts are:

$$0, 1, 2, \dots, \left\lfloor \frac m2 \right\rfloor$$

The number of integers in that range is:

$$\left\lfloor \frac m2 \right\rfloor + 1$$

Substitute $m=\frac n2$:

$$\left\lfloor \frac{n}{4} \right\rfloor + 1$$

So the full answer is:

$$\begin{cases} 0, & n \text{ is odd} \\ \left\lfloor \frac n4 \right\rfloor + 1, & n \text{ is even} \end{cases}$$

Checking Samples

For $n=4$:

• $w=0 \Rightarrow c=2$
• $w=1 \Rightarrow c=0$

Answer: $2$.

For $n=6$:

• $w=0 \Rightarrow c=3$
• $w=1 \Rightarrow c=1$

Answer: $2$.

For $n=100$:

$$\left\lfloor \frac{100}{4} \right\rfloor + 1 = 25+1=26$$

Answer: $26$.

Complexity

Each test case is solved with one parity check and one division.

Time complexity: $O(1)$ per test case.

Memory complexity: $O(1)$.

Tiny problem, tiny formula. Beautiful. Annoyingly easy to overcomplicate, though.