Grid Paths

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 64M

Author:

ChrisT

Problem type

In a grid of size $W$ ~W~ by $H$ ~H~ $(1 \leq W,H \leq 10^6)$ ~(1 \leq W,H \leq 10^6)~, you are to determine the amount of paths from the square $(1,1)$ ~(1,1)~ to the square $(W,H)$ ~(W,H)~ that do not go through $X$ ~X~ blocked off squares only moving to the right or up. $(0 \leq X \leq 2)$ ~(0 \leq X \leq 2)~.

Input Specification

The first line will contain three integers, $W$ ~W~, $H$ ~H~, and $X$ ~X~.

The next $X$ ~X~ lines will contain two integers $x$ ~x~ and $y$ ~y~. $(1 \leq x \leq W)$ ~(1 \leq x \leq W)~ $(1 \leq y \leq H)$ ~(1 \leq y \leq H)~

Output Specification

On one line, you are to output the number of valid paths through the grid modulo $10^9 + 7$ ~10^9 + 7~.

Subtasks

Subtask 1 [20%]

$X = 0$ ~X = 0~

Subtask 2 [30%]

$X = 1$ ~X = 1~

Subtask 3 [50%]

$X = 2$ ~X = 2~

Sample Input

4 4 0

Sample Output

Comments

-5

Moose19_GFSS_14 commented on Jan. 30, 2020, 6:51 p.m.

literally, copy of CCC 2012 S5

This comment is hidden due to too much negative feedback. Show it anyway.

2

Moose19_ApplebyCollege_1 commented on Feb. 2, 2020, 3:35 p.m.

Have you looked at the constraints? They're nowhere near similar

2

_ commented on Jan. 30, 2020, 11:59 p.m.

Well you can't solve either, so does it really matter?

0

wleung_bvg commented on Dec. 24, 2019, 7:38 p.m.

Seems to be an easier version of https://codeforces.com/contest/559/problem/C.

Interesting problem though!