codeforces-scrape

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

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  ![](https://espresso.codeforces.com/400eaf050728a66f50543d34c2092f38739f042d.png) 
     84 
     85 The second and third balls will drop as follows.
     86 
     87  ![](https://espresso.codeforces.com/77ef1a0328f131a7144ce7bea0c05aafd01e7dc3.png) 
     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.