← 返回题目列表

AtCoder · agc055_a

A. ABC 身份

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个字符串 S 长度 3N,恰好包含 N 字母 A, N 字母 B,和 N 字母 C.

让我们调用一个字符串 T 由字母组成 A, B,和 C 好,如果满足以下条件:

  • 的长度 T 可以被整除 3。我们将其表示为 3K.
  • T_1 = T_2 = \ldots = T_K
  • T_{K+1} = T_{K+2} = \ldots = T_{2K}
  • T_{2K+1} = T_{2K+2} = \ldots = T_{3K}.
  • 信件 T_1, T_{K+1} 和 T_{2K+1} 彼此不同。

好的字符串的例子是 ABC, BBAACC,和 AAACCCBBB.

想办法分割 S 进入 最多 6 (不一定是连续的)子序列,以便每个子序列中的字母形成一个好的字符串。

可以证明,在问题的约束下,总是可能的。

约束

  • 1 \le N \le 2\cdot 10^5
  • 字符串 S 包含 N 字母 A, N 字母 B,和 N 字母 C.

输入

输入由标准输入按以下格式给出:

N
S

输出

输出一个长度的字符串 3N,仅包含来自 1 to 6。 对于每一个 1\le i \le 6 出现在你的字符串中,字符 S 在您输出的位置 i 必须形成良好的字符串。 如果有多种可能的解决方案,则打印其中任何一个都将被认为是正确的。


示例输入 1

2
ABCCBA

示例输出 1

111222

S 被分成子序列 ABC 和 CBA,每个都是一个好字符串。


示例输入 2

4
AABCBCAACBCB

示例输出 2

111211241244

的位置 1 形成一个子序列 AABBCC,位置 2 形成一个子序列 CAB,以及位置 4 形成一个子序列 ACB。 所有这些字符串都很好。