codeforces-scrape

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

1986B.md (3084B)


      1 Source: https://codeforces.com/problemset/problem/1986/B
      2 
      3 B. Matrix Stabilization
      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 You are given a matrix of size $n \times m$, where the rows are numbered from $1$ to $n$ from top to bottom, and the columns are numbered from $1$ to $m$ from left to right. The element at the intersection of the $i$-th row and the $j$-th column is denoted by $a_{ij}$.
     22 
     23 Consider the algorithm for stabilizing matrix $a$:
     24 
     25 1. Find the cell $(i, j)$ such that its value is strictly greater than the values of all its neighboring cells. If there is no such cell, terminate the algorithm. If there are multiple such cells, choose the cell with the smallest value of $i$, and if there are still multiple cells, choose the one with the smallest value of $j$.
     26 2. Set $a_{ij} = a_{ij} - 1$.
     27 3. Go to step $1$.
     28 
     29 In this problem, cells $(a, b)$ and $(c, d)$ are considered neighbors if they share a common side, i.e., $|a - c| + |b - d| = 1$.
     30 
     31 Your task is to output the matrix $a$ after the stabilization algorithm has been executed. It can be shown that this algorithm cannot run for an infinite number of iterations.
     32 
     33 Input
     34 
     35 Each test consists of multiple sets of input data. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of sets of input data. This is followed by their description.
     36 
     37 The first line of each set of input data contains two integers $n$ and $m$ ($1 \leq n, m \leq 100, n \cdot m \gt 1$) — the number of rows and columns of matrix $a$.
     38 
     39 The next $n$ lines describe the corresponding rows of the matrix. The $i$-th line contains $m$ integers $a_{i1}, a_{i2}, \ldots, a_{im}$ ($1 \leq a_{ij} \leq 10^9$).
     40 
     41 It is guaranteed that the sum of $n \cdot m$ over all sets of input data does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each set of input data, output $n$ lines with $m$ numbers in each line — the values of the cells of matrix $a$ after the stabilization algorithm.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 6
     53 
     54 1 2
     55 
     56 3 1
     57 
     58 2 1
     59 
     60 1
     61 
     62 1
     63 
     64 2 2
     65 
     66 1 2
     67 
     68 3 4
     69 
     70 2 3
     71 
     72 7 4 5
     73 
     74 1 8 10
     75 
     76 5 4
     77 
     78 92 74 31 74
     79 
     80 74 92 17 7
     81 
     82 31 17 92 3
     83 
     84 74 7 3 92
     85 
     86 7 31 1 1
     87 
     88 3 3
     89 
     90 1000000000 1 1000000000
     91 
     92 1 1000000000 1
     93 
     94 1000000000 1 1000000000
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 1 1 
    101 1 
    102 1 
    103 1 2 
    104 3 3 
    105 4 4 5 
    106 1 8 8 
    107 74 74 31 31 
    108 74 74 17 7 
    109 31 17 17 3 
    110 31 7 3 3 
    111 7 7 1 1 
    112 1 1 1 
    113 1 1 1 
    114 1 1 1
    115 ```
    116 
    117 Note
    118 
    119 In the first set of input data, the algorithm will select the cell $(1, 1)$ twice in a row and then terminate.
    120 
    121  ![](https://espresso.codeforces.com/4fb67cacd44fc282a22834a916612099b73944ec.png) 
    122 
    123 In the second set of input data, there is no cell whose value is strictly greater than the values of all neighboring cells.
    124 
    125 In the third set of input data, the algorithm will select the cell $(2, 2)$ and then terminate.
    126 
    127  ![](https://espresso.codeforces.com/aa9bd0c452993dee06dfd201c5ebf32191300904.png) 
    128 
    129 In the fourth set of input data, the algorithm will select the cell $(1, 1)$ three times and then the cell $(2, 3)$ twice.
    130 
    131  ![](https://espresso.codeforces.com/cd610d02f268dd1f49435964d3b84fc0174827ac.png)