codeforces-scrape

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

2152B.md (3833B)


      1 Source: https://codeforces.com/problemset/problem/2152/B
      2 
      3 B. Catching the Krug
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 1024 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Doran and the Krug are playing a game on a grid consisting of $(n + 1) \times (n + 1)$ cells whose coordinates are pairs of integers from $0$ to $n$, inclusive. The Krug's goal is not to be caught by Doran for as long as possible, while Doran's goal is to catch the Krug as early as possible. We say Doran caught the Krug if they stand on the same grid cell.
     22 
     23 To play the game, the Krug and Doran take turns alternately, starting from the Krug:
     24 
     25 * The Krug can either stay in the same cell or move to a cell vertically or horizontally (but not diagonally) adjacent. Formally, if the Krug is currently at the cell $(a, b)$, she can stay at $(a, b)$ or move to either $(a-1, b), (a, b-1), (a, b+1), (a+1, b)$.
     26 * Doran can either stay in the same cell or move to a cell vertically, horizontally, or diagonally adjacent. Formally, if Doran is currently at the cell $(c, d)$, he can stay at $(c, d)$ or move to either $(c-1, d-1), (c-1, d), (c-1, d+1), (c, d-1), (c, d+1), (c+1, d-1), (c+1, d), (c+1, d+1)$.
     27 * Both players cannot go outside of the grid.
     28 
     29  ![](https://espresso.codeforces.com/389b09213658c44ba4b0550db897796229b5ae0d.png) Figures showing possible movements of the Krug and Doran. Letters 'K' and 'D' represent the current position of the Krug and Doran, and the colored cells represent possible positions each player can move to in their respective turn. 
     30 
     31 The Krug's survival time is defined as the number of Doran's turns until Doran catches the Krug for the given starting cells of the players. Assuming that both players play optimally, find the Krug's survival time or report that the Krug can survive for infinite turns.
     32 
     33 Input
     34 
     35 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.
     36 
     37 Each test case consists of a single line containing five integers $n$, $r_K$, $c_K$, $r_D$, and $c_D$ ($1 \le n \le 10^9$, $0 \le r_K, c_K, r_D, c_D \le n$, $(r_K, c_K) \ne (r_D, c_D)$) — $n$ is the size of the grid, $(r_K, c_K)$ represents the Krug's starting cell, and $(r_D, c_D)$ represents Doran's starting cell.
     38 
     39 Output
     40 
     41 For each test case, output the Krug's survival time when both players play optimally. If the Krug can survive for infinite turns, print $-1$.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 7
     49 
     50 2 0 0 1 1
     51 
     52 3 1 1 0 1
     53 
     54 1 1 0 0 1
     55 
     56 6 1 3 3 2
     57 
     58 9 4 1 4 2
     59 
     60 82 64 2 63 2
     61 
     62 1000000000 500000000 500000000 1000000000 0
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1
     69 
     70 3
     71 
     72 1
     73 
     74 4
     75 
     76 2
     77 
     78 19
     79 
     80 1000000000
     81 ```
     82 
     83 Note
     84 
     85 Explanation of the first test case:
     86 
     87 The Krug starts at $(0,0)$ and Doran starts at $(1,1)$. On the Krug's turn, she can only move to $(0,0)$, $(0,1)$, or $(1,0)$.
     88 
     89 Doran, starting at $(1,1)$, can reach any cell on the $3 \times 3$ grid in a single move. Therefore, no matter where the Krug moves, Doran can always move to her cell on his first turn. The Krug's survival time is $1$.
     90 
     91  ![](https://espresso.codeforces.com/4918e8c6206a329d6afd98791f4a2535c62fb198.png) 
     92 
     93 Explanation of the second test case:
     94 
     95 The Krug starts at $(1,1)$ and Doran at $(0,1)$. To survive Doran's first turn, the Krug must move to a cell that Doran cannot reach. The only such cell is $(2,1)$.
     96 
     97 After the Krug moves to $(2,1)$, Doran moves to $(1,1)$ to get closer.
     98 
     99 Now, for her second move, the Krug must again move to a cell Doran can't reach, which is $(3,1)$. Doran then moves to $(2,1)$.
    100 
    101 At this point, no matter where the Krug moves for her third turn, Doran can always reach her cell. It can be shown that this is an optimal strategy for both, and therefore the Krug's survival time is $3$.
    102 
    103  ![](https://espresso.codeforces.com/884d3355d039dc35594ce536d991cb8093ce1bc0.png)