codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2217C.md (3155B)


      1 Source: https://codeforces.com/problemset/problem/2217/C
      2 
      3 C. Grid Covering
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Prakul has been working hard setting problems for Codecraft. When he's deep in thought, he likes jumping around his room in weird but specific ways. After some time, he wonders if jumping in this manner can cover all the tiles of his room.
     22 
     23 Prakul's room can be considered as a grid $A$ consisting of $n$ rows and $m$ columns. He starts walking from $A_{1,1}$. If he is currently at $A_{i,j}$ he can do either of the following moves:
     24 
     25 * Jump $b$ steps right to $A_{\,i,\;((j+b-1)\bmod m)+1}$, or
     26 * Jump $a$ steps down to $A_{\,((i+a-1)\bmod n)+1,\;j}$.
     27 
     28 A special restriction is that he can start with either move, but must alternate between them.
     29 
     30 Note that his room is quite special as it wraps around itself. Moving one step right from the $m$-th column places him in the $1$-st column. Similarly, moving one step down from the $n$-th row places him in the $1$-st row.
     31 
     32 Since he still has to work on problemsetting, he needs your help. Determine if he can visit all tiles in $A$ in a finite number of jumps.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     37 
     38 The only line of each test case contains four integers $n, m, a, b$ ($1 \leq n, m, a, b\leq 10^{9}$).
     39 
     40 Output
     41 
     42 For each test case, print "YES" if Prakul can cover all the tiles of his room, and "NO" otherwise.
     43 
     44 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 10
     52 
     53 1 1 1 1
     54 
     55 2 2 1 1
     56 
     57 4 2 2 1
     58 
     59 6 9 6 7
     60 
     61 67 42 42 67
     62 
     63 3411 4134 32 23
     64 
     65 90234 143124 232 323
     66 
     67 69387963 98793214 9791 4324786
     68 
     69 985865 578977 899368 447605
     70 
     71 1000000000 1000000000 1000000000 1000000000
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 YES
     78 
     79 YES
     80 
     81 NO
     82 
     83 NO
     84 
     85 YES
     86 
     87 NO
     88 
     89 NO
     90 
     91 NO
     92 
     93 YES
     94 
     95 NO
     96 ```
     97 
     98 Note
     99 
    100 In the second test case: $n=2$, $m=2$, $a=1$, $b=1$. One possible way to cover the grid is if Prakul starts by moving down:
    101 
    102 * Start at $(1, 1)$.
    103 * Jump down $a=1$ tile: $(1, 1) \to (2, 1)$.
    104 * Jump right $b=1$ tile: $(2, 1) \to (2, 2)$.
    105 * Jump down $a=1$ tile: $(2, 2) \to (1, 2)$.
    106 * Jump right $b=1$ tile: $(1, 2) \to (1, 1)$.
    107 
    108 The sequence of visited tiles is $\{(1, 1), (2, 1), (2, 2), (1, 2)\}$. In this case, all $2 \cdot 2 = 4$ tiles are covered, so the answer would be "YES". Notice that Prakul wraps around the grid in the last two moves.
    109 
    110 In the third test case: $n=4$, $m=2$, $a=2$, $b=1$. If Prakul starts by moving down, the moves look like:
    111 
    112 * Start at $(1, 1)$.
    113 * Jump down $a=2$ tiles: $(1, 1) \to (3, 1)$.
    114 * Jump right $b=1$ tile: $(3, 1) \to (3, 2)$.
    115 * Jump down $a=2$ tiles: $(3, 2) \to (1, 2)$.
    116 * Jump right $b=1$ tile: $(1, 2) \to (1, 1)$.
    117 * $\cdots$
    118 
    119 In this case, the tiles $\{(2, 1), (2, 2), (4, 1), (4, 2)\}$ remain unvisited forever. Since not all tiles can be covered, the answer is "NO". It can be shown that even if Prakul started by moving right in the first move, the answer would not have changed.