Back To School '19: Parkour

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 128M

Author:

Problem type

Wesley is running late to school!

The neighbourhood is modelled as a coordinate plane, and Wesley's house is currently sitting at $(0, 0)$ $(0, 0)$ . The school is a rectangle of dimensions $H$ $H$ metres horizontally and $V$ $V$ metres vertically. Its bottom left corner is situated at $(X, Y)$ $(X, Y)$ , but there are entrances located at any point of the school. Formally, there are entrances located at all points $(x_i, y_i)$ $(x_{i}, y_{i})$ such that $X \le x_i < X+H$ $X \leq x_{i} < X + H$ and $Y \le y_i < Y+V$ $Y \leq y_{i} < Y + V$ .

Being the cool kid that he is, Wesley does a lot of parkour and will use his abilities to move faster than most people. In one second, he can move in one of two ways:

Move $2$ $2$ metres up, then $1$ $1$ metre right
Move $1$ $1$ metre up, then $2$ $2$ metres right

Hurry, the bell rings in $T$ $T$ seconds! Can Wesley make it to class strictly before $T$ $T$ seconds pass and the teachers get angry at him?

Note that Wesley can only enter the school if he touches an entrance to the school after performing a move.

Python users are recommended to use PyPy over CPython. There is a significant performance increase.

Input Specification

The first line of the input will contain four integers $X, Y, H, V$ $X, Y, H, V$ $(1 \le X, Y, H, V \le 10^7)$ $(1 \leq X, Y, H, V \leq 10^{7})$ , the coordinates of the bottom left corner of the school and its dimensions.
The second line of the input will contain one integer $T$ $T$ $(1 \le T \le 10^7)$ $(1 \leq T \leq 10^{7})$ , the number of seconds Wesley has before the school bell rings.

It is guaranteed that the school will not be located directly at Wesley's house and that it will be reachable using the moves described.

Output Specification

If Wesley can parkour in time to school (in strictly less than $T$ $T$ seconds), output YES. Otherwise, output NO.

Constraints

Subtask 1 [30%]

$X, Y, H, V, T \le 200$ $X, Y, H, V, T \leq 200$

Subtask 2 [70%]

No additional constraints.

Sample Input 1

Copy

2 3 3 3
2

Sample Output 1

Copy

NO

Explanation For Sample 1

While it is possible for Wesley to reach the school in $2$ $2$ seconds:

Move $1$ $1$ metre up, move $2$ $2$ metres right to $(2, 1)$ $(2, 1)$
Move $2$ $2$ metres up, move $1$ $1$ metre right to $(3, 3)$ $(3, 3)$

The bell would ring by the time he gets there, making it impossible.

Sample Input 2

Copy

2 3 3 3
3

Sample Output 2

Copy

YES

Explanation For Sample 2

This time, Wesley has enough time to make it before the bell rings, making the trip now possible.

Comments

2

Narcariel commented on Feb. 6, 2020, 12:07 a.m.

Damn, this problem is very difficult. I think it should be 7 points instead of 5.

-1

pblpbl commented on Oct. 17, 2019, 2:11 a.m.

What's test case #28?

0

ross_cleary commented on Jan. 1, 2021, 11:50 p.m.

My issue with case 28 is that I was counting a negative number of moves as valid, which obviously isn't possible.

-1

pblpbl commented on Oct. 15, 2019, 9:06 p.m.

Anyone know why my code doesn't work?

-3
hxxr commented on Oct. 15, 2019, 11:08 p.m.
Not enough corner case testing.

Copy
10 10 1 1 8

If you do it by hand you can see it is in fact possible to get to school in this case by simply using 4 of one move and 3 of the other move.

3

injust commented on Oct. 16, 2019, 9:11 p.m.

Doesn't this bring him to either $(11, 10)$ $(11, 10)$ or $(10, 11)$ $(10, 11)$ , neither of which are entrances?

0

hxxr commented on Oct. 16, 2019, 11:18 p.m.

Yeah oops I just got confused about the formal definition because my submission using the correct condition fails but my submission using the wrong condition works.

0

pblpbl commented on Oct. 16, 2019, 8:52 p.m.

Can you explain how you would get to school in this case?

7

Joyous commented on Sept. 11, 2019, 3:20 a.m. ← edited →

This is my favourite problem! Thanks Zeyu!

11

Zeyu commented on Sept. 11, 2019, 10:10 a.m.

Happy to hear that, thanks :)