TLE '17 Contest 2 P6 - Save Jody!

View as PDF

Submit solution


Points:20 (partial)
Time limit:6.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 \leq i \leq 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 \leq S < H \leq 200

1 \leq L \leq 10^9

0 \leq N \leq 250 \times H

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

Subtask Constraint Score
1 H,L\leq 5 10
2 H \leq 100, L \leq 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


Report an issue

Comments

There are no comments at the moment.