codeforces-scrape

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

1737C.md (2788B)


      1 Source: https://codeforces.com/problemset/problem/1737/C
      2 
      3 C. Ela and Crickets
      4 
      5 time limit per test
      6 
      7 1 second
      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 |  |  |
     22 | --- | --- |
     23 |  | Ela likes Chess a lot. During breaks, she usually challenges her co-worker in DTL to some chess games. She's not an expert at classic chess, but she's very interested in Chess variants, where she has to adapt to new rules and test her tactical mindset to win the game. |
     24 
     25 The problem, which involves a non-standard chess pieces type that is described below, reads: given $3$ white crickets on a $n \cdot n$ board, arranged in an "L" shape next to each other, there are no other pieces on the board. Ela wants to know with a finite number of moves, can she put any white cricket on the square on row $x$, column $y$?
     26 
     27 An "L"-shape piece arrangement can only be one of the below:
     28 
     29 |  |  |
     30 | --- | --- |
     31 |  |  |
     32 
     33 |  |  |
     34 | --- | --- |
     35 |  |  |
     36 
     37 For simplicity, we describe the rules for crickets on the board where only three white crickets are. It can move horizontally, vertically, or diagonally, but only to a square in some direction that is immediately after another cricket piece (so that it must jump over it). If the square immediately behind the piece is unoccupied, the cricket will occupy the square. Otherwise (when the square is occupied by another cricket, or does not exist), the cricket isn't allowed to make such a move.
     38 
     39 See an example of valid crickets' moves on the pictures in the Note section.
     40 
     41 Input
     42 
     43 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.
     44 
     45 The first line of each test case contains $n$ ($4 \le n \le 10^5$) — denotes the size of the chessboard.
     46 
     47 The second line of each test case contains 6 numbers: $r_1$, $c_1$, $r_2$, $c_2$, $r_3$, $c_3$ ($1 \le r_1, c_1, r_2, c_2, r_3, c_3 \le n$) — coordinates of the crickets. The input ensures that the three crickets are arranged in an "L" shape that the legend stated.
     48 
     49 The third line of each test case contains 2 numbers: $x$, $y$ ($1 \le x, y \le n$) — coordinates of the target square.
     50 
     51 Output
     52 
     53 For each test case, print "YES" or "NO" to denotes whether Ela can put a cricket on the target square.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 6
     61 
     62 8
     63 
     64 7 2 8 2 7 1
     65 
     66 5 1
     67 
     68 8
     69 
     70 2 2 1 2 2 1
     71 
     72 5 5
     73 
     74 8
     75 
     76 2 2 1 2 2 1
     77 
     78 6 6
     79 
     80 8
     81 
     82 1 1 1 2 2 1
     83 
     84 5 5
     85 
     86 8
     87 
     88 2 2 1 2 2 1
     89 
     90 8 8
     91 
     92 8
     93 
     94 8 8 8 7 7 8
     95 
     96 4 8
     97 ```
     98 
     99 Output
    100 
    101 ```
    102 YES
    103 NO
    104 YES
    105 NO
    106 YES
    107 YES
    108 ```
    109 
    110 Note
    111 
    112 Here's the solution for the first test case. The red square denotes where the crickets need to reach. Note that in chess horizontals are counted from bottom to top, as well as on this picture.
    113 
    114  ![](https://espresso.codeforces.com/9738589dc2b914e26931f4ae4ad9f0cdcb562855.png)