TLE '17 Contest 2 P6 - Save Jody!

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types
Can Fax escape in time?

Fax McClad, Croneria's most heroic bounty hunter has learned that Space Pirates have captured his friend Jody and locked her up in a power plant! Fax was able to free her, but the Space Pirates activated the power plant's self-destruct mechanism!

Hopping on his Kyuwing with Jody, Fax begins to fly through a long escape tunnel. From a top-down view, the tunnel can be represented as a 2-D grid which is H blocks tall by L+1 blocks wide. Coordinates range from (0, 0) to (L, H-1). Fax initially begins at (0, S), and needs to fly to (L, i) for any 0 \le i \le H-1. In order to go as fast as possible due to the exploding plant behind him, Fax will only fly (1, 0), (1, 1), or (1, -1).

However, the explosions have activated N blast pillars. Fax obviously cannot fly through a pillar. Suppose that Fax is currently in (x,y). If (x+1,y) and (x+1,y+1) contain pillars, then Fax can move to (x,y+1) if it does not contain a pillar. Similarly, if (x+1,y) and (x+1,y-1) contain pillars, then Fax can move to (x,y-1) if it does not contain a pillar.

In summary,

  • Fax will not fly through a pillar.
  • Fax has the choice to fly (1, 0), (1, 1), or (1, -1).
  • If Fax is at (x,y) and there are pillars at (x+1,y) and (x+1,y+1), Fax has the choice to fly (0, 1).
  • If Fax is at (x,y) and there are pillars at (x+1,y) and (x+1,y-1), Fax has the choice to fly (0, -1).

In addition, Fax is never allowed to move to the same location as he previously was. There are at most 250 unique x positions across all the pillars.

Please find out how many ways there are for Fax to get to the end before the power plant blows up!

Constraints

For all subtasks:

0 \le S < H \le 200

1 \le L \le 10^9

0 \le N \le 250 \times H

If a pillar is at (x,y), then 1 \le x \le L-1 and 0 \le y \le H-1.

Subtask Constraint Score
1 H,L \le 5 10
2 H \le 100, L \le 10^5 30
3 No additional restrictions 60

Input Specification

The first line will contain the integers N,H,L,S.

This will be followed by N pairs of integers, indicating the positions for each of the pillars.

Output Specification

Print a single integer, the number of ways for Fax to go to the end modulo 10^9+7.

Sample Input 1

2 2 5 0
1 1
4 0

Sample Output 1

8

Sample Explanation 1

Sample Input 2

2 2 3 1
1 0
2 1

Sample Output 2

2

Sample Explanation 2

Sample Input 3

4 5 3 0
2 0
2 1
2 2
2 3

Sample Output 3

4

Sample Explanation 3


Comments

There are no comments at the moment.