跟随字母AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a string $S$ of length $N$ consisting of lowercase English letters. Let $S_i$ denote the $i$-th character of $S$.
给定一个由小写英文字母组成的长度为 $N$ 的字符串 $S$。令 $S_i$ 表示 $S$ 的第 $i$ 个字符。AI (CI翻译)
There are $N$ islands arranged in a circle, numbered island $1$, island $2$, $\ldots$, island $N$ in clockwise order. In particular, the island clockwise-adjacent to island $N$ is island $1$. The character $S_i$ is written on island $i$. Initially, there is one person on each island.
有 $N$ 个岛屿排列成一个圆环，按照顺时针方向依次编号为岛屿 $1$、岛屿 $2$、$\ldots$、岛屿 $N$。特别地，岛屿 $N$ 顺时针方向相邻的岛屿是岛屿 $1$。字符 $S_i$ 写在岛屿 $i$ 上。初始时，每个岛屿上都有一个人。AI (CI翻译)
You can perform the following operation zero or more times.
你可以进行零次或多次以下操作。AI (CI翻译)
- Choose one character
$c$that appears in$S$. Every person departs from the island they are currently on and moves one island at a time in the clockwise direction. Each person stops as soon as they first arrive, after departing, at an island on which the character$c$is written. Even if the island a person is currently on has the character$c$written on it, that person still departs.
- 选择一个在
$S$中出现的字符$c$。所有人都从当前所在的岛屿出发，并沿顺时针方向每次移动一个岛屿。每个人在出发后，第一次到达写有字符$c$的岛屿时立即停下。即使某人当前所在的岛屿上写有字符$c$，该人仍然会出发。
Let $K$ be the minimum possible number of islands that have one or more people on them after all operations are finished.
令 $K$ 为完成所有操作后，至少有一个人所在的岛屿数量的最小值。AI (CI翻译)
Find $K$, and a sequence of operations that makes the number of islands with one or more people equal to $K$ after the operations.
求出 $K$，以及一个操作序列，使得完成所有操作后，至少有一个人所在的岛屿数量恰好为 $K$。AI (CI翻译)
Under the constraints of this problem, it can be proved that there always exists a sequence of operations of length at most $10^6$ that makes the number of islands with one or more people equal to $K$.
在本题的约束条件下，可以证明总是存在一个长度不超过 $10^6$ 的操作序列，使得完成所有操作后，至少有一个人所在的岛屿数量恰好为 $K$。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \le N \le 1000$$S$is a string of length$N$consisting of lowercase English letters.$N$is an integer.
$1 \le N \le 1000$$S$是一个由长度为$N$的小写英文字母组成的字符串。$N$是整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入由标准输入给出，格式如下：AI (CI翻译)
N
SN
SOutput
输出格式
AI (CI翻译)Let $L$ be an integer representing the number of operations, and let $X$ be a string representing the sequence of operations. Output in the following format:
令 $L$ 为表示操作次数的整数，令 $X$ 为表示操作序列的字符串。请按照以下格式输出：AI (CI翻译)
K
L
XK
L
XIf $L=0$, output the third line as an empty line.
如果 $L=0$，请将第三行输出为空行。AI (CI翻译)
$L$ must satisfy $0 \le L \le 10^6$.
$L$ 必须满足 $0 \le L \le 10^6$。AI (CI翻译)
$X$ must be a string of length $L$ consisting of characters that appear in $S$, and the $i$-th character of $X$ represents the character chosen in the $i$-th operation.
$X$ 必须是一个长度为 $L$、且仅由在 $S$ 中出现的字符组成的字符串，$X$ 的第 $i$ 个字符表示第 $i$ 次操作中选择的字符。AI (CI翻译)
After performing the operations according to the sequence $X$, the number of islands with one or more people must be $K$.
按照操作序列 $X$ 执行操作后，至少有一个人所在的岛屿数量必须为 $K$。AI (CI翻译)
If multiple outputs satisfy the conditions, you may output any of them.
如果有多个输出满足条件，可以输出其中任意一个。AI (CI翻译)
样例
4
abca
1
1
b
4
aabb
1
2
ab
4
aaaa
4
0
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。