P6285 [COCI 2016/2017 #1] Jetpack

Mirko is playing a small game. In a $10$-row, $n$-column grid, he needs to start from the bottom-left corner, avoid landing on obstacles, and finally reach any position in column $n$. Each second, he moves one unit to the right. In the game, Mirko has a jetpack (turned off at the start): - When the jetpack is turned on, each second he additionally moves one unit upward (i.e. he moves up-right), until he reaches the top row of the grid. - When the jetpack is turned off, each second he additionally moves one unit downward (i.e. he moves down-right), until he reaches the bottom row of the grid. He may turn on the jetpack at any second, and turn it off after any number of seconds. This is considered one operation. Now, Mirko wants you to design a sequence of operations so that he can finish the game successfully.

The first line contains an integer $n$, the number of columns of the grid. The next $10$ lines each contain $n$ characters, describing whether there is an obstacle at each position. Each character is either `.` or `X`. - `.` means there is no obstacle in that cell. - `X` means there is an obstacle in that cell.

**This problem uses Special Judge**. The first line contains a non-negative integer $p$, the number of operations Mirko should perform. The next $p$ lines each contain two positive integers $t_i$ and $x_i$, meaning that Mirko should turn on the jetpack at second $t_i$ and turn it off after $x_i$ seconds. If multiple answers exist, output any one of them. Additionally: - Operations must be given in chronological order, and no other operation may be performed before the current one finishes, i.e. $t_i+x_i\le t_{i+1}$. - After the game ends, Mirko cannot perform any operations, i.e. $t_i

#### Explanation of Sample 1 The figure below shows the path represented by the sample output. ``` .....XX...X ....XX...XX ...XX...XX. ........... ....XXX.... .....*...*. ....*X*.*.* ...*XX.*.X. ..*XX...XX. **.X...XX.. ``` --- #### Constraints For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^5$. The testdata guarantees that at least one solution exists that allows Mirko to finish the game successfully. ------------ #### Notes **Translated from [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T2 Jetpack_**。 Translated by ChatGPT 5