How long will it take for the horse to be captured?

Question

Source: https://open.kattis.com/problems/ambush

Problem: When Farmer Oskar doesn’t watch his cows closely enough, they tend to wander off into the forest to hunt for horse spies. To catch an enemy agent horse, the cows lure it into a cow trail and set up fences at the endpoints of the trail, which are $L$ meters apart. Two previously hidden cows then reveal themselves, having concealed themselves in nearby bushes – and the chase is on! The cows are located at positions $A$ and $B$ meters from the left endpoint.

One particular horse (positioned $P$ meters from the left endpoint) who they attempted to catch remembered to bring her walkie-talkie and have now called for backup. The backup will arrive to rescue her very soon, so she wonders for how long she can hold the cows off.

Horse chasing happens in $1$ minute steps. During each minute, the following steps happen in order:

1. The cows choose to move either $0$ or $1$ meters, in any direction.

2. The horse jumps either $0$, $1$, or $2$ meters in any direction. However, if a cow occupies the same position as the horse, she can only jump a single meter since she now must jump over the cow.

3. If there is a cow in the same position as the horse, the cows capture her.

How long will it take for the horse to be captured, assuming both she and the cows move optimally?

Parameters:

$1 \leq L \leq 1000$

$0 \leq A \leq L$

$0 \leq B \leq L$

$0 \leq P \leq L$

$A \neq B \neq P$

Answer 1

Some initial thoughts, not a fully fleshed-out solution:

the way the cows catch the horse is to get (and stay) next to each other and then force the horse up against the fence at one end of the trail. Once they are next to each other there's nothing the horse can do to stop them from advancing one space per minute until it's caught. At first guess it feels like they can mostly just ignore what the horse is doing and just focus on moving towards each other as quickly as possible. The horse will want to get and stay between the two cows as long as possible, and at the last moment jump to whichever side is further from the end of the trail.

So roughly speaking, it'll take about |(B-A)/2| minutes for the cows to get next to each other, and then another X minutes to trap the horse, where X is the distance from the cows' meeting point to the further side of the trail.