codeforces-scrape

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

2109B.md (2819B)


      1 Source: https://codeforces.com/problemset/problem/2109/B
      2 
      3 B. Slice to Survive
      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 Duelists Mouf and Fouad enter the arena, which is an $n \times m$ grid!
     22 
     23 Fouad's monster starts at cell $(a, b)$, where rows are numbered $1$ to $n$ and columns $1$ to $m$.
     24 
     25 Mouf and Fouad will keep duelling until the grid consists of only one cell.
     26 
     27 In each turn:
     28 
     29 * Mouf first cuts the grid along a row or column line into two parts, discarding the part without Fouad's monster. Note that the grid must have at least two cells; otherwise, the game has already ended.
     30 * After that, in the same turn, Fouad moves his monster to any cell (possibly the same one it was in) within the remaining grid.
     31 
     32  ![](https://espresso.codeforces.com/8b1099cc13f7e0c8fbf449b3e7f2fcd1c9eec0b9.png) Visualization of the phases of the fourth test case. 
     33 
     34 Mouf wants to minimize the number of turns, while Fouad wants to maximize them. How many turns will this epic duel last if both play optimally?
     35 
     36 Input
     37 
     38 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.
     39 
     40 The first and only line of each test case contains four integers $n$, $m$, $a$, and $b$ ($2 \le n, m \le 10^9$, $1 \le a \le n$, $1 \le b \le m$) — denoting the number of rows, the number of columns, the starting row of the monster, and the starting column of the monster, respectively.
     41 
     42 Output
     43 
     44 For each test case, output a single integer — the number of turns this epic duel will last if both play optimally.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 8
     52 
     53 2 2 1 1
     54 
     55 3 3 2 2
     56 
     57 2 7 1 4
     58 
     59 2 7 2 2
     60 
     61 8 9 4 6
     62 
     63 9 9 5 5
     64 
     65 2 20 2 11
     66 
     67 22 99 20 70
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 2
     74 4
     75 4
     76 3
     77 6
     78 8
     79 6
     80 10
     81 ```
     82 
     83 Note
     84 
     85 In the first test case, one possible duel sequence is as follows:
     86 
     87 * Turn 1: Mouf cuts the grid horizontally along the line between the rows $1$ and $2$, removing the bottom half and leaving a $1 \times 2$ grid.
     88 * Turn 1: Fouad's monster is at the cell $(1,1)$.
     89 * Turn 2: Mouf cuts the $1 \times 2$ grid again, removes one column, and isolates the cell $(1,1)$.
     90 
     91 The duel is completed in $2$ turns.
     92 
     93 In the fourth case, one possible duel sequence is as follows:
     94 
     95 * Turn 1: Mouf cuts the grid vertically along the line between the columns $2$ and $3$, splitting it into a $2 \times 2$ and a $2 \times 5$ field, then removes the $2 \times 5$ part.
     96 * Turn 1: Fouad moves the monster to the cell $(1,1)$.
     97 * From this point on, the duel plays out just like the first test case—two more turns trim down the grid from $2 \times 2$ to a single $1 \times 1$ cell.
     98 
     99 In total, the duel is completed in $3$ turns.
    100 
    101 You can refer to the pictures mentioned in the problem statement for illustrations of the fourth test case.