P4441 [COCI 2017/2018 #3] Retro

Little Mirko got a video game console for Christmas. It wasn’t a Playstation 4 or an Xbox one, but Atari 2600, and it came with one free game. The protagonist of the game is standing on the bottom of the screen, and there are various objects dispersed on the rest of the screen, falling towards the bottom. More precisely, the screen can be represented as a grid of RxS pixels arranged in R rows and S columns. The protagonist takes up one pixel of the lowest line and is marked with ‘M’. The rest of the pixels are marked with some of the characters: ‘.’ (empty space), ‘*’ (bomb), ‘(‘ (open bracket) or ‘)’ (closed bracket). The protagonist can move one pixel to the left or to the right in a single move, but doesn’t need to, whereas the rest of the objects simultaneously move one pixel down (possibly out of the screen). When the protagonist finds himself at the same position as one of the brackets, we say that he picked up that bracket and added it at the end of his array of acquired brackets. The protagonist’s goal is to acquire the longest possible **valid** bracket expression. A valid bracket expression is defined inductively in the following way: - “()” is a valid expression - If **a​** is a valid expression, then “(**a**​)” is a valid expression as well - If **a​** and **b​** are valid expressions, then “**ab**​” is a valid expression as well The game ends when the protagonist finds himself at the same position as the bomb, or when all the objects fall out of the screen.

无

无

In test cases worth 25% of total points, it will hold 1 ≤ R ≤ 15. In test cases worth 50% of total points, it will hold 1 ≤ R ≤ 100. If you output the correct length, but the wrong expression, you will be awarded 40% of points for that test case. In any case, in order to score points, your output must consist of two non-empty lines. ~~(但我并不会做spj，所以这话屁用没有)~~ **Clarification​ ​of​ ​the​ ​first​ ​test​ ​case**:​ ​The protagonist’s moves are: left, left, right right. **Clarification​ ​of​ ​the​ ​second​ ​test​ ​case**:​ ​The protagonist’s moves are: stay still, stay still, stay still, right, left. **Clarification​ ​of​ ​the​ ​third​ ​test​ ​case**:​ ​The protagonist’s moves are: stay still, stay still, right.