Waterloo 2022 Fall E - Water Flow

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 256M

Problem type
2022 Fall Waterloo Local Contest, Problem E

After wrapping up the work on electric grids, Thomas Edison set his sight on another industry to disrupt - water transportation. Specifically, he aims to find solutions to connect water stations to houses with a limited set of pipes available in cases where the competition is unable to do so. The types of pipes available to use can be seen in the picture below. From left to right they are: corner pipe, cross pipe, straight pipe, and T-shape pipe. Since mister Edison is quite busy, that task has been assigned to a junior employee at his company - you!

We'll model the problem as follows - given an infinite 2D grid, the water station is located at square (X_{start}, Y_{start}) and the target house is at (X_{finish}, Y_{finish}). The start and finish tiles are guaranteed to be different, and the only type of pipe you can install there is a cross pipe. You'll be given a fixed number of pipes of each type, and your goal is to build a continuous path from start to finish using those components. Once that is accomplished, we'll solder open pipes that lead to nowhere and start running the water. While building your path, each piece of pipe can be rotated by 90 degrees any number of times. Unfortunately, sometimes such a path cannot be built. Thus, your first task is to determine whether such a path exists or not.

Constraints

0 \le X_{start}, Y_{start}, X_{finish}, Y_{finish} \le 10^{10}

0 \le n_1, n_3, n_4 \le 10^{10}

2 \le n_2 \le 10^{10}

Input Specification

First line of input contains (X_{start}, Y_{start}) (space separated).

Second line of input contains (X_{finish}, Y_{finish}) (space separated).

The last line of input contains n_1, n_2, n_3, n_4 - the number of corner pipes, cross pipes, straight pipes, and T-shape pipes available.

Output Specification

Print Yes if the task can be accomplished and No if not.

Sample Input 1

8 7
14 3
3 2 6 0

Sample Output 1

Yes

Sample Input 2

8 7
14 3
1 2 7 0

Sample Output 2

No

Comments

There are no comments at the moment.