Back To School '19: Parkour

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 128M

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). The school is a rectangle of dimensions H metres horizontally and V metres vertically. Its bottom left corner is situated at (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) such that X \le x_i < X+H and Y \le 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 metres up, then 1 metre right
  • Move 1 metre up, then 2 metres right

Hurry, the bell rings in T seconds! Can Wesley make it to class strictly before 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 (1 \le X, Y, H, V \le 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 (1 \le T \le 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 seconds), output YES. Otherwise, output NO.


Subtask 1 [30%]

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

Subtask 2 [70%]

No additional constraints.

Sample Input 1

2 3 3 3

Sample Output 1


Explanation For Sample 1

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

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

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

Sample Input 2

2 3 3 3

Sample Output 2


Explanation For Sample 2

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


  • 1
    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.

      10 10 1 1

      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.

  • 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 :)