CF1060G Balls and Pockets

There is a strip with an infinite number of cells. Cells are numbered starting with $ 0 $ . Initially the cell $ i $ contains a ball with the number $ i $ . There are $ n $ pockets located at cells $ a_1, \ldots, a_n $ . Each cell contains at most one pocket. Filtering is the following sequence of operations: - All pockets at cells $ a_1, \ldots, a_n $ open simultaneously, which makes balls currently located at those cells disappear. After the balls disappear, the pockets close again. - For each cell $ i $ from $ 0 $ to $ \infty $ , if the cell $ i $ contains a ball, we move that ball to the free cell $ j $ with the lowest number. If there is no free cell $ j < i $ , the ball stays at the cell $ i $ . Note that after each filtering operation each cell will still contain exactly one ball. For example, let the cells $ 1 $ , $ 3 $ and $ 4 $ contain pockets. The initial configuration of balls is shown below (underscores display the cells with pockets): 0 1 2 3 4 5 6 7 8 9 ... After opening and closing the pockets, balls 1, 3 and 4 disappear: 0 2 5 6 7 8 9 ... After moving all the balls to the left, the configuration looks like this: 0 2 5 6 7 8 9 10 11 12 ... Another filtering repetition results in the following: 0 5 8 9 10 11 12 13 14 15 ... You have to answer $ m $ questions. The $ i $ -th of these questions is "what is the number of the ball located at the cell $ x_i $ after $ k_i $ repetitions of the filtering operation?"

N/A

N/A