1575J.md (2282B)
1 Source: https://codeforces.com/problemset/problem/1575/J 2 3 J. Jeopardy of Dropped Balls 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Mr. Chanek has a new game called Dropping Balls. Initially, Mr. Chanek has a grid $a$ of size $n \times m$ 22 23 Each cell $(x,y)$ contains an integer $a_{x,y}$ denoting the direction of how the ball will move. 24 25 * $a_{x,y}=1$ — the ball will move to the right (the next cell is $(x, y + 1)$); 26 * $a_{x,y}=2$ — the ball will move to the bottom (the next cell is $(x + 1, y)$); 27 * $a_{x,y}=3$ — the ball will move to the left (the next cell is $(x, y - 1)$). 28 29 Every time a ball leaves a cell $(x,y)$, the integer $a_{x,y}$ will change to $2$. Mr. Chanek will drop $k$ balls sequentially, each starting from the first row, and on the $c_1, c_2, \dots, c_k$-th ($1 \leq c_i \leq m$) columns. 30 31 Determine in which column each ball will end up in (position of the ball after leaving the grid). 32 33 Input 34 35 The first line contains three integers $n$, $m$, and $k$ ($1 \leq n, m \leq 1000$, $1 \leq k \leq 10^5$) — the size of the grid and the number of balls dropped by Mr. Chanek. 36 37 The $i$-th of the next $n$ lines contains $m$ integers $a_{i,1},a_{i,2},\ldots,a_{i,m}$ ($1 \leq a_{i,j} \leq 3$). It will satisfy $a_{i, 1} \ne 3$ and $a_{i, m} \ne 1$. 38 39 The next line contains $k$ integers $c_1, c_2, \ldots, c_k$ ($1 \leq c_i \leq m$) — the balls' column positions dropped by Mr. Chanek sequentially. 40 41 Output 42 43 Output $k$ integers — the $i$-th integer denoting the column where the $i$-th ball will end. 44 45 Examples 46 47 Input 48 49 ``` 50 5 5 3 51 1 2 3 3 3 52 2 2 2 2 2 53 2 2 2 2 2 54 2 2 2 2 2 55 2 2 2 2 2 56 1 2 1 57 ``` 58 59 Output 60 61 ``` 62 2 2 1 63 ``` 64 65 Input 66 67 ``` 68 1 2 2 69 1 3 70 1 2 71 ``` 72 73 Output 74 75 ``` 76 1 2 77 ``` 78 79 Note 80 81 In the first example, the first ball will drop as follows. Note that the cell $(1, 1)$ will change direction to the bottom direction. 82 83  84 85 The second and third balls will drop as follows. 86 87  88 89 All balls will be dropped from the first row and on the $c_1, c_2, \dots, c_k$-th columns respectively. A ball will stop dropping once it leaves the grid.