codeforces-scrape

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

1941D.md (3915B)


      1 Source: https://codeforces.com/problemset/problem/1941/D
      2 
      3 D. Rudolf and the Ball Game
      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 Rudolf and Bernard decided to play a game with their friends. $n$ people stand in a circle and start throwing a ball to each other. They are numbered from $1$ to $n$ in the clockwise order.
     22 
     23 Let's call a transition a movement of the ball from one player to his neighbor. The transition can be made clockwise or counterclockwise.
     24 
     25 Let's call the clockwise (counterclockwise) distance from player $y_1$ to player $y_2$ the number of transitions clockwise (counterclockwise) that need to be made to move from player $y_1$ to player $y_2$. For example, if $n=7$ then the clockwise distance from $2$ to $5$ is $3$, and the counterclockwise distance from $2$ to $5$ is $4$.
     26 
     27 Initially, the ball is with the player number $x$ (players are numbered clockwise). On the $i$-th move the person with the ball throws it at a distance of $r_i$ ($1 \le r_i \le n - 1$) clockwise or counterclockwise. For example, if there are $7$ players, and the $2$nd player, after receiving the ball, throws it a distance of $5$, then the ball will be caught by either the $7$th player (throwing clockwise) or the $4$th player (throwing counterclockwise). An illustration of this example is shown below.
     28 
     29  ![](https://espresso.codeforces.com/3839c7a125c21f6555bcdb3ac6b10e676b4f5c07.png) 
     30 
     31 The game was interrupted after $m$ throws due to unexpected rain. When the rain stopped, the guys gathered again to continue. However, no one could remember who had the ball. As it turned out, Bernard remembered the distances for each of the throws and the direction for some of the throws (clockwise or counterclockwise).
     32 
     33 Rudolf asks you to help him and based on the information from Bernard, calculate the numbers of the players who could have the ball after $m$ throws.
     34 
     35 Input
     36 
     37 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follow the descriptions of the test cases.
     38 
     39 The first line of each test case contains three integers $n, m, x$ ($2 \le n \le 1000$, $1 \le m \le 1000$, $1 \le x \le n$) — the number of players, the number of throws made, and the number of the player who threw the ball first, respectively.
     40 
     41 The next $m$ lines contain information about each throw in order. Each of them contains an integer $r_i$ ($1 \le r_i \le n - 1$) — the distance at which the $i$-th throw was made, and a symbol $c_i$, equal to '0', '1', or '?':
     42 
     43 * if $c_i$='0', then the $i$-th throw was made clockwise,
     44 * if $c_i$='1', then the $i$-th throw was made counterclockwise,
     45 * if $c_i$='?', then Bernard does not remember the direction and the $i$-th throw could have been made either clockwise or counterclockwise.
     46 
     47 It is guaranteed that the sum $n \cdot m$ ($n$ multiplied by $m$) over all test cases does not exceed $2 \cdot 10^5$.
     48 
     49 Output
     50 
     51 For each test case, output two lines.
     52 
     53 In the first line, output the number of players $k$ ($1 \le k \le n$) who could have the ball at the end of the game.
     54 
     55 In the next line, output $k$ numbers $b_i$ ($1 \le b_i \le n$) — the numbers of the players in increasing order. All numbers must be different.
     56 
     57 Example
     58 
     59 Input
     60 
     61 ```
     62 5
     63 
     64 6 3 2
     65 
     66 2 ?
     67 
     68 2 ?
     69 
     70 2 ?
     71 
     72 12 1 2
     73 
     74 3 1
     75 
     76 10 7 4
     77 
     78 2 ?
     79 
     80 9 1
     81 
     82 4 ?
     83 
     84 7 0
     85 
     86 2 0
     87 
     88 8 1
     89 
     90 5 ?
     91 
     92 5 3 1
     93 
     94 4 0
     95 
     96 4 ?
     97 
     98 1 ?
     99 
    100 4 1 1
    101 
    102 2 ?
    103 ```
    104 
    105 Output
    106 
    107 ```
    108 3
    109 2 4 6 
    110 1
    111 11 
    112 4
    113 3 5 7 9 
    114 3
    115 2 3 5 
    116 1
    117 3
    118 ```
    119 
    120 Note
    121 
    122 Below is an illustration of three throws for the first test case. The arrows denote possible throw directions. Players who could have the ball after the throw are highlighted in gray.
    123 
    124  ![](https://espresso.codeforces.com/facec0e73193578aea46a4045fbd7b9d3ded40de.png) ![](https://espresso.codeforces.com/5a3a9d0fe33eff8ebcbb17c795d9aa82cee18935.png) ![](https://espresso.codeforces.com/9ca276927532adea0682a7875ded9538dcbef9fd.png)