Mock CCC '22 1 S5 - Berkeley Math Tournament Awards Ceremony

Points: 35 (partial)

Time limit: 0.25s

Memory limit: 1G

Problem type

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

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

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

Constraints

$1 \le N, M \le 100$ ~1 \le N, M \le 100~

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

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

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

Input Specification

The first line contains two integers, $N$ ~N~ and $M$ ~M~.

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

The next line contains one integer, $Q$ ~Q~.

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

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

Output Specification

Output $Q$ ~Q~ lines. On the $i$ ~i~th line, output yes if $(0, 0)$ ~(0, 0)~ is reachable. Otherwise, output no.

Sample Input 1

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

Sample Output 1

yes
no
no
yes
yes

Comments

-2

ColonelBy_team10 commented on Dec. 31, 2021, 3:51 p.m.

X Y is misleading, as it connotes an reference to Cartesian Coordinates. X, Y is actually Row, Then Column, which is Y, X in the cartesian system.

0

ColonelBy_team10 commented on Dec. 30, 2021, 3:31 p.m.

If x is negative, then r is negative. Which item in the template grid would a negative r be referring to?

1

xiaowuc1 commented on Jan. 1, 2022, 1:56 a.m.

This problem is using the convention that the remainder must be nonnegative and less than the divisor. This is a widely accepted convention which comes into conflict with certain programming language standards - however, contextually it should be clear that this is the definition being used.