codeforces-scrape

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

2228B.md (2080B)


      1 Source: https://codeforces.com/problemset/problem/2228/B
      2 
      3 B. Remilia Plays Soku
      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 Remilia is trying to escape, while Reimu wants to land the final hit.
     22 
     23 The playing field consists of $n$ positions arranged in a circle. For each $1 \le i \lt n$, positions $i$ and $i+1$ are adjacent, and positions $1$ and $n$ are also adjacent.
     24 
     25 Initially, at time $0$, Reimu is at position $x_1$ and Remilia is at position $x_2$, where $x_1 \ne x_2$.
     26 
     27 Each second, the following happens in order:
     28 
     29 1. Remilia either moves to an adjacent position or stays in place. Over the entire game, she may move to an adjacent position at most $k$ times.
     30 2. After observing Remilia's action, Reimu either moves to an adjacent position or stays in place.
     31 3. If they are at the same position after both actions, Reimu catches Remilia and the game ends.
     32 
     33 Assuming both players play optimally, Reimu always tries to minimize the catching time, while Remilia tries to maximize it.
     34 
     35 Find the number of seconds until Reimu catches Remilia.
     36 
     37 Input
     38 
     39 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.
     40 
     41 The only line of each test case contains four integers $n$, $x_1$, $x_2$ and $k$ ($2\le n\le10^8$, $1\le x_1,x_2\le n$, $x_1\ne x_2$, $0\le k\le 10^8$).
     42 
     43 Output
     44 
     45 For each test case, output the number of seconds until Reimu catches Remilia, assuming both players play optimally.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 
     54 2 1 2 0
     55 
     56 4 3 2 1
     57 
     58 4 2 3 1
     59 
     60 16 8 4 2
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 1
     67 
     68 2
     69 
     70 2
     71 
     72 6
     73 ```
     74 
     75 Note
     76 
     77 In the first test case, one possible sequence of actions is:
     78 
     79 * In the first second, Remilia stays in place, and then Reimu moves to $2$ and catches Remilia.
     80 
     81 In the second test case, one possible sequence of actions is:
     82 
     83 * In the first second, Remilia moves to $1$, and then Reimu moves to $2$.
     84 * In the second second, Remilia cannot move and has to stay in place, and then Reimu moves to $1$ and catches Remilia.