← 返回题目列表

Codeforces · 1009/B

B. 最小三进制字符串

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

给你一个三元字符串(它是一个仅由字符“0”、“1”和“2”组成的字符串)。

您可以交换任意两个相邻(连续)字符“0”和“1”(即将“01”替换为“10”,反之亦然)或任意两个相邻(连续)字符“1”和“2”(即将“12”替换为“21”,反之亦然)。

例如,对于字符串“010210”,我们可以执行以下操作:

- "010210" $$$\rightarrow$$$ "100210";
- "010210" $$$\rightarrow$$$ "001210";
- "010210" $$$\rightarrow$$$ "010120";
- “010210”$$$\rightarrow$$$“010201”。

请注意,您不能交换“02”$$$\rightarrow$$$“20”,反之亦然。除了上述之外,您不能对给定字符串执行任何其他操作。

您的任务是通过使用这些交换任意次数(可能为零)来获取最小可能(按字典顺序)的字符串。

如果存在某个位置 $$$i$$$($$$1 \le i \le |a|$$$,其中 $$$|s|$$$ 是字符串 $$$s$$$ 的长度),则字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$(如果字符串 $$$a$$$ 和 $$$b$$$ 具有相同的长度),这样对于每个$$$j < i$$$ 成立 $$$a_j = b_j$$$,且 $$$a_i < b_i$$$。

输入

输入的第一行包含字符串 $$$s$$$,仅由字符 '0'、'1' 和 '2' 组成,其长度在 $$$1$$$ 和 $$$10^5$$$ 之间(含)。

输出

打印单个字符串 - 通过使用上述交换任意次数(可能为零)可以获得的最小可能(按字典顺序)字符串。

示例

输入 #1

100210

输出 #1

001120

输入 #2

11222121

输出 #2

11112222

输入 #3

20

输出 #3

20