A5955. 「ROIR 2021 Day 1」基因突变
编程题
普及-
知识点
题目描述
**译自 [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)**。
我们规定，一个合法的基因串仅包括
我们规定，任何一个合法基因串都有一个压缩串，压缩串将原基因字符串中连续的字母压缩成这个字母的个数后跟这个字母，个数如为 $1$，则省略。
例子：
现在有一个合法基因串 $S$，其压缩串为 $T$，您可以对这个合法基因串做一次操作，操作可以有如下三种：
- 在 $S$ 的第 $x$ 个字符后插入一个字符 $Z$。
- 删除 $S$ 的第 $x$ 个字符。
- 将 $S$ 的第 $x$ 个字符替换为另一个字符 $Z$。
设 $S$ 经过操作后变为 $S'$，$S'$ 的压缩串为 $T'$，求使得 $T'$ 的长度最小化或最大化的一种操作方案。
我们规定，一个合法的基因串仅包括
A、G、C 与 T。我们规定，任何一个合法基因串都有一个压缩串，压缩串将原基因字符串中连续的字母压缩成这个字母的个数后跟这个字母，个数如为 $1$，则省略。
例子：
AAAAACAAAAACC 的压缩串为 5AC5A2C。现在有一个合法基因串 $S$，其压缩串为 $T$，您可以对这个合法基因串做一次操作，操作可以有如下三种：
- 在 $S$ 的第 $x$ 个字符后插入一个字符 $Z$。
- 删除 $S$ 的第 $x$ 个字符。
- 将 $S$ 的第 $x$ 个字符替换为另一个字符 $Z$。
设 $S$ 经过操作后变为 $S'$，$S'$ 的压缩串为 $T'$，求使得 $T'$ 的长度最小化或最大化的一种操作方案。
输入格式
仅一行一个字符串 $T$。
输出格式
输出共两行，第一行为使 $T'$ 长度最小化的一种方案，第二行为使 $T'$ 长度最大化的一种方案。
方案输出格式如下：
- 如果您想要使用 $1$ 操作，输出格式类似
- 如果您想要使用 $2$ 操作，输出格式类似
- 如果您想要使用 $3$ 操作，输出格式类似
方案输出格式如下：
- 如果您想要使用 $1$ 操作，输出格式类似
1 x Z。- 如果您想要使用 $2$ 操作，输出格式类似
2 x。- 如果您想要使用 $3$ 操作，输出格式类似
3 x Z。输入输出样例
输入 #1
5AC5A2C
输出 #1
3 6 A 1 2 C
说明/提示
对于所有子任务，有 $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$ |
| 子任务编号 | 数据范围 | 分值 |
| :-----------: | :------------------------------------: | :-----: |
| $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$ |