[CCO 2022] Good Game

Luogu
IDLGP10055
Time1000ms
Memory1000MB
DifficultyP7
2022Special JudgeCCO(加拿大)
Finn 正在玩一个叫做 Twos and Threes 的游戏。Twos and Threes 是一个单人游戏,它在一维棋盘上进行。在初始位置,有 $N$ 个方块排成一行,每个方块标有 $\tt{A}$ 或 $\tt{B}$。方块从左到右编号为 $1$ 到 $N$。Finn 可以进行以下操作: - 选择 $2$ 或 $3$ 个连续的方块,它们有相同的标签,将它们从棋盘上移除并将剩余的方块连接起来,从左到右重新编号方块。 如果棋盘上的所有方块都被移除,Finn 就赢得了游戏。你的任务是帮助 Finn 确定一个赢得游戏的操作序列,或者确定游戏无法获胜。 ## Input 第一行包含一个整数 $N$。 第二行包含一个字符串 $S$,表示游戏开始时的标签。$S$ 中有 $N$ 个字符,$S$ 中的每个字符都是 $\tt{A}$ 或 $\tt{B}$。 ## Output 如果存在赢得游戏的操作序列,第一行输出 $K$,即移动序列中的移动次数。在接下来的 $K$ 行中,输出两个空格分隔的整数 $i,j$ 表示移除位于 $[i,i+j-1]$ 的方块的一次操作。 如果没有赢得游戏的操作序列,输出 $-1$。 如果有多个赢得游戏的操作序列,你可以输出任何一个。 [samples] ## Note ## 样例解释 操作如下: $$ \begin{aligned} &\tt{ABAAB\underline{BB}AA}\\ &\tt{AB\underline{AA}BAA}\\ &\tt{A\underline{BB}AA}\\ &\tt{\underline{AAA}}\\ \end{aligned} $$ ## 数据范围 对于所有的数据,有 $1 \leq N \leq 10^{6}$。 子任务编号|分值|$N$ 的范围 :-:|:-:|:-: $1$|$12$|$1 \leq N \leq 15$ $2$|$24$|$1 \leq N \leq 300$ $3$|$28$|$1 \leq N \leq 6000$ $4$|$36$|$1 \leq N \leq 10^6$
Samples
Input #1
9
ABAABBBAA
Output #1
4
6 2
3 2
2 2
1 3
API Response (JSON)
{
  "problem": {
    "name": "[CCO 2022] Good Game",
    "description": {
      "content": "Finn 正在玩一个叫做 Twos and Threes 的游戏。Twos and Threes 是一个单人游戏,它在一维棋盘上进行。在初始位置,有 $N$ 个方块排成一行,每个方块标有 $\\tt{A}$ 或 $\\tt{B}$。方块从左到右编号为 $1$ 到 $N$。Finn 可以进行以下操作: - 选择 $2$ 或 $3$ 个连续的方块,它们有相同的标签,将它们从棋盘上移除并将剩余的方块连接起",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1024000
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10055"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Finn 正在玩一个叫做 Twos and Threes 的游戏。Twos and Threes 是一个单人游戏,它在一维棋盘上进行。在初始位置,有 $N$ 个方块排成一行,每个方块标有 $\\tt{A}$ 或 $\\tt{B}$。方块从左到右编号为 $1$ 到 $N$。Finn 可以进行以下操作:\n\n- 选择 $2$ 或 $3$ 个连续的方块,它们有相同的标签,将它们从棋盘上移除并将剩余的方块连接起...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments