Mock CCC '22 S5 - Berkeley Math Tournament Awards Ceremony

View as PDF

Submit solution

Points: 35 (partial)
Time limit: 0.25s
Memory limit: 1G

Problem type

Kaitlyn is the tournament director for the Berkeley Math Tournament, a tournament so large that Kaitlyn runs it on an infinite 2D plane.

The 2D plane is templatized by an N \times M rectangle R, the top-left corner being (0, 0) and the bottom-right corner being (N-1, M-1). Square (x, y) has an obstacle if and only if square (r, s) in the template rectangle has an obstacle, where r and s are respectively remainders when x and y are divided by N and M. One can only travel directly between two squares if their Manhattan distance is 1 and both are empty.

Kaitlyn is running the awards ceremony at (0, 0). She wishes to know for Q distinct empty points (x_i, y_i) whether someone at (x_i, y_i) can travel to (0, 0) without running into any obstacles.


1 \le N, M \le 100

1 \le Q \le 2 \cdot 10^5

|x_i|, |y_i| \le 10^9

In tests worth 1 mark, Q \le 10^3.

Input Specification

The first line contains two integers, N and M.

The next N lines contain a string of M characters, each character being either . if it is empty or # if it contains an obstacle.

The next line contains one integer, Q.

The next Q lines contain two integers, x_i and y_i, indicating a query point (x_i, y_i).

The input is set such that each of these points and (0, 0) will not contain an obstacle.

Output Specification

Output Q lines. On the ith line, output yes if (0, 0) is reachable. Otherwise, output no.

Sample Input 1

6 9
1 4
5 4
1 -5
5 -5
-1000000000 0

Sample Output 1



There are no comments at the moment.