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

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 \leq N, M \leq 100$

$1 \le Q \le 2 \cdot 10^5$ $1 \leq Q \leq 2 \cdot 10^{5}$

$|x_i|, |y_i| \le 10^9$ $| x_{i} |, | y_{i} | \leq 10^{9}$

In tests worth 1 mark, $Q \le 10^3$ $Q \leq 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

Copy

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

Sample Output 1

Copy

yes
no
no
yes
yes

Comments

-3

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.