FARMLEGS - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N legs in total on a farm, each from a cow (4 legs) or chicken (2 legs).
What’s the minimum possible number of animals that can be on the farm?

EXPLANATION:

Cows have more legs than chickens, so for the minimum possible number of animals, ideally there would be more cows than chickens.
In fact, you may notice that two chickens can be replaced with a single cow for the same number of legs, so we’ll never have more than one chicken.

So, a simple greedy strategy works: take as many cows as possible; and if two legs remain in the end we’ll need one chicken.
That is,

  • If N is a multiple of 4, the answer is just \frac{N}{4}, taking all cows.
  • Otherwise, since N is even, it must be two more than a multiple of 4.
    In this case, the answer is \frac{N-2}{4} + 1, since N-2 legs can be evenly distributed to cows and the remaining two go to a chicken.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    ans = n//4
    if n%4 == 2: ans += 1
    print(ans)