[ROIR 2021] 基因突变 (Day 1)

Luogu

IDLGP9763

Time1000ms

Memory128MB

DifficultyP4

2021Special JudgeROIR（俄罗斯）

我们规定，一个合法的基因串仅包括 `A`、`G`、`C` 与 `T`。我们规定，任何一个合法基因串都有一个压缩串，压缩串将原基因字符串中连续的字母压缩成这个字母的个数后跟这个字母，个数如为 $1$，则省略。例子：`AAAAACAAAAACC` 的压缩串为 `5AC5A2C`。现在有一个合法基因串 $S$，其压缩串为 $T$，您可以对这个合法基因串做一次操作，操作可以有如下三种： - 在 $S$ 的第 $x$ 个字符后插入一个字符 $Z$。 - 删除 $S$ 的第 $x$ 个字符。 - 将 $S$ 的第 $x$ 个字符替换为另一个字符 $Z$。设 $S$ 经过操作后变为 $S'$，$S'$ 的压缩串为 $T'$，求使得 $T'$ 的长度最小化或最大化的一种操作方案。 ## Input 一行一个字符串 $T$。 ## Output 输出共两行，第一行为使 $T'$ 长度最小化的一种方案，第二行为使 $T'$ 长度最大化的一种方案。方案输出格式如下： - 如果您想要使用 $1$ 操作，输出格式类似 `1 x Z`。 - 如果您想要使用 $2$ 操作，输出格式类似 `2 x`。 - 如果您想要使用 $3$ 操作，输出格式类似 `3 x Z`。 [samples] ## Background **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day1 T3 [ Изменённая ДНК](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day1.pdf)**。 ## Note 【样例解释】： $S=$ `AAAAACAAAAACC`。使用 `3 6 A` 的操作后 $S'=$ `AAAAAAAAAAACC`，$T'=$ `11A2C`。使用 `1 2 C` 的操作后 $S'=$ `AACAAACAAAAACC`，$T'=$ `2AC3AC5A2C`。【数据范围】：对于所有子任务，有 $1\le |T|\le 10^5$，$1\le |S|\le 10^9$。 | 子任务编号 |数据范围| 分值 | |:-:|:-:|:-:| |$1$|$\lvert T\rvert\le \lvert S\rvert\le 10$|$9$ | |$2$|$\lvert T\rvert\le 100$，$\lvert S\rvert\le 10^4$|$17$| |$3$|$\lvert T\rvert\le 10^3$，$\lvert S\rvert\le 10^5$|$21$| |$4$|$\lvert S\rvert\le 10^7$|$11$| |$5$|无特殊限制|$42$|

Samples

Input #1

5AC5A2C

Output #1

3 6 A
1 2 C

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2021] 基因突变 (Day 1)",
    "description": {
      "content": "我们规定，一个合法的基因串仅包括 `A`、`G`、`C` 与 `T`。 我们规定，任何一个合法基因串都有一个压缩串，压缩串将原基因字符串中连续的字母压缩成这个字母的个数后跟这个字母，个数如为 $1$，则省略。 例子：`AAAAACAAAAACC` 的压缩串为 `5AC5A2C`。 现在有一个合法基因串 $S$，其压缩串为 $T$，您可以对这个合法基因串做一次操作，操作可以有如下三种： - ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9763"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "我们规定，一个合法的基因串仅包括 `A`、`G`、`C` 与 `T`。\n\n我们规定，任何一个合法基因串都有一个压缩串，压缩串将原基因字符串中连续的字母压缩成这个字母的个数后跟这个字母，个数如为 $1$，则省略。\n\n例子：`AAAAACAAAAACC` 的压缩串为 `5AC5A2C`。\n\n现在有一个合法基因串 $S$，其压缩串为 $T$，您可以对这个合法基因串做一次操作，操作可以有如下三种：\n\n- ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments