第 78 场 AtCoder Grand Contest
重排 ABCAI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given strings $S$ and $T$ of length $3N$, each containing exactly $N$ occurrences of each of A, B, and C.
给定字符串 $S$ 和 $T$，它们的长度均为 $3N$，且各自恰好包含 $N$ 个 A、$N 个 B 和 $N 个 C。AI (CI翻译)
You can perform the following operation zero or more times.
你可以进行零次或多次以下操作：AI (CI翻译)
- Choose one substring of
$S$whose characters are all distinct. - Sort the characters of the chosen substring in ascending order.
- 选择
$S$的一个子串，要求其中的字符互不相同。 - 将所选子串中的字符按升序排序。
Determine whether it is possible to make $S$ equal to $T$, and if it is possible, find the minimum number of operations required.
请判断能否将 $S$ 变为 $T$。如果可以，求所需的最少操作次数。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \le N \le 100$$S$and$T$are strings of length$3N$consisting ofA,B, andC.- Each of
$S$and$T$contains exactly$N$occurrences of each ofA,B, andC. - All input values are integers.
$1 \le N \le 100$$S$和$T$是由A、B、C组成的长度为$3N$的字符串。$S$和$T$各自恰好包含$N$个A、$N$个B和$N$个C。- 输入的所有值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N
S
TN
S
TOutput
输出格式
AI (CI翻译)Output the answer. If it is impossible to make $S$ equal to $T$, output -1.
输出答案。如果无法将 $S$ 变为 $T$，输出 -1。AI (CI翻译)
样例
Input #1
2
CACBAB
ACABCB
Output #1
2
For example, you can make $S$ equal to $T$ by performing two operations as follows.
- Choose the first two characters of `CACBAB`, making it `ACCBAB`.
- Choose the $3$-rd through $5$-th characters of `ACCBAB`, making it `ACABCB`.
It is impossible to make them equal with one operation, so the answer is $2$.
Input #2
1
ABC
CBA
Output #2
-1
No matter how you perform the operations, you cannot make `ABC` equal to `CBA`.
Input #3
8
CCBCCCABCCAABBBACABAAABB
BCAAACCABCCBACBBBACAABCB
Output #3
32
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。