Problem J3: Exactly Electrical

Time limit: 1 second

Problem DescriptionCopy Anchor Link

You live in Grid City, which is composed of integer-numbered streets which run east-west (parallel to the $x$-axis) and integer-numbered avenues which run north-south (parallel to the $y$-axis). The streets and avenues have infinite length, and there is a street for every integer $y$-coordinate and an avenue for every $x$-coordinate. All intersections are labelled by their integer coordinates: for example, avenue 7 and street -3 intersect at (7,-3).

You drive a special electric car which uses up one unit of electrical charge moving between adjacent intersections: that is, moving either north or south to the next street, or moving east or west to the next avenue). Until your battery runs out, at each intersection, your car can turn left, turn right, go straight through, or make a U-turn. You may visit the same intersection multiple times on the same trip.

Suppose you know your starting intersection, your destination intersection and the number of units of electrical charge in your battery. Determine whether you can travel from the starting intersection to the destination intersection using the charge available to you in such a way that your battery is empty when you reach your destination.

Input SpecificationCopy Anchor Link

The input consists of three lines. The first line contains $a$ followed by $b$, indicating the starting coordinate $(a,b)$ $(-1000 \leq a \leq 1000; -1000 \leq b \leq 1000)$.

The second line contains $c$ followed by $d$, indicating the destination coordinate $(c,d)$ $(-1000 \leq c \leq 1000; -1000 \leq d \leq 1000)$.

The third line contains an integer $t$ $(0 \leq t \leq 10\ 000)$ indicating the initial number of units of electrical charge of your battery.

For 3 of the 15 available marks, $0 \leq a, b, c, d \leq 2$.

For an additional 3 of the 15 marks available, $t \leq 8$.

Output SpecificationCopy Anchor Link

Output Y if it is possible to move from the starting coordinate to the destination coordinate using exactly $t$ units of electrical charge. Otherwise output N.

Sample Input 1Copy Anchor Link

3 4
3 3
3

Output for Sample Input 1Copy Anchor Link

Y

Explanation for Output for Sample Input 1Copy Anchor Link

One possibility is to travel from $(3,4)$ to $(4,4)$ to $(4, 3)$ to $(3,3)$.

Sample Input 2Copy Anchor Link

10 2
10 4
5

Output for Sample Input 2Copy Anchor Link

N

Explanation for Output for Sample Input 2Copy Anchor Link

It is possible to get from $(10,2)$ to $(10,4)$ using exactly 2 units of electricity, by going north 2 units.

It is also possible to travel using 4 units of electricity as in the following sequence: $$(10,2) \rightarrow (10,3) \rightarrow (11,3) \rightarrow (11,4) \rightarrow (10,4).$$ It is also possible to travel using 5 units of electricity from $(10,2)$ to $(11,4)$ by the following sequence: $$(10,2) \rightarrow (10,3) \rightarrow (11,3) \rightarrow (12,3) \rightarrow (12,4) \rightarrow (11,4).$$ It is not possible to move via any path of length 5 from $(10,2)$ to $(10,4)$, however.