Canadian Computing Olympiad: 2022 Day 2, Problem 3

Finn is playing a game of Twos and Threes. Twos and Threes is a one-player game played on a one-dimensional board. In the starting position, there are ~N~ blocks arranged in a row, with each block labelled either ~A~ or ~B~. Blocks are numbered from ~1~ to ~N~ from left to right. Finn is allowed to make moves of the following form:

• Select ~2~ or ~3~ consecutive blocks that share the same label. Remove them from the board. Connect any remaining blocks together. Re-index the blocks from left to right, starting with index ~1~.

Finn wins the game if all blocks are removed from the board. Your task is to help Finn determine a winning sequence of moves, or determine if the game cannot be won.

Input Specification

The first line of input will contain the integer ~N~.

The second line of input will contain the string ~S~, which is the starting position of the game.

There are ~N~ characters in ~S~, and each of these characters in ~S~ is either A or B.

Marks Awarded	Bounds on ~N~
~3~ marks	~1 \le N \le 15~
~6~ marks	~1 \le N \le 300~
~7~ marks	~1 \le N \le 6\,000~
~9~ marks	~1 \le N \le 10^6~

Output Specification

If there is a winning sequence of moves, output ~K~, the number of moves in the winning sequence. On each of the next ~K~ lines, print an index ~i~, followed by one space, followed by a number ~j~, denoting a move that will remove the blocks currently at indices ~i~ to ~i+j-1~, inclusive.

If there is no winning sequence of moves, output -1.

If there are multiple winning sequences, then any winning sequence will be accepted. There is no need to minimize or maximize ~K~.

Sample Input

9
ABAABBBAA

Possible Output for Sample Input

4
6 2
3 2
2 2
1 3

Explanation of Output for Sample Input

The sample output denotes this winning sequence:

$$\displaystyle \begin{align*} & ABAAB\underline{BB}AA \\ & AB\underline{AA}BAA \\ & A\underline{BB}AA \\ & \underline{AAA} \end{align*}$$