B. Minimum Ternary String

Codeforces

IDCF1009B

Time1000ms

Memory256MB

Difficulty—

greedyimplementation

English · Original

Chinese · Translation

Formal · Original

You are given a ternary string (it is a string which consists only of characters '_0_', '_1_' and '_2_'). You can swap any two adjacent (consecutive) characters '_0_' and '_1_' (i.e. replace "_01_" with "_10_" or vice versa) or any two adjacent (consecutive) characters '_1_' and '_2_' (i.e. replace "_12_" with "_21_" or vice versa). For example, for string "_010210_" we can perform the following moves: * "_010210_" $\rightarrow$ "_100210_"; * "_010210_" $\rightarrow$ "_001210_"; * "_010210_" $\rightarrow$ "_010120_"; * "_010210_" $\rightarrow$ "_010201_". Note than you cannot swap "_02_" $\rightarrow$ "_20_" and vice versa. You cannot perform any other operations with the given string excluding described above. You task is to obtain the minimum possible (lexicographically) string by using these swaps arbitrary number of times (_possibly, zero_). String $a$ is lexicographically less than string $b$ (if strings $a$ and $b$ have the same length) if there exists some position $i$ ($1 \le i \le |a|$, where $|s|$ is the length of the string $s$) such that for every $j < i$ holds $a_j = b_j$, and $a_i < b_i$. ## Input The first line of the input contains the string $s$ consisting only of characters '_0_', '_1_' and '_2_', its length is between $1$ and $10^5$ (inclusive). ## Output Print a single string — the minimum possible (lexicographically) string you can obtain by using the swaps described above arbitrary number of times (_possibly, zero_). [samples]

给你一个三元字符串（即仅由字符 '_0_'、'_1_' 和 '_2_' 组成的字符串）。你可以交换任意两个相邻（连续）的字符 '_0_' 和 '_1_'（即用 "_10_" 替换 "_01_"，或反之亦然），或者交换任意两个相邻（连续）的字符 '_1_' 和 '_2_'（即用 "_21_" 替换 "_12_"，或反之亦然）。例如，对于字符串 "_010210_"，我们可以执行以下操作：注意，你不能交换 "_02_" $arrow.r$ "_20_" 及其反向。除了上述操作外，你不能对给定字符串执行任何其他操作。你的任务是通过任意次（可能为零次）使用这些交换操作，获得字典序最小的字符串。字符串 $a$ 字典序小于字符串 $b$（当字符串 $a$ 和 $b$ 长度相同时）是指存在某个位置 $i$（$1 lt.eq i lt.eq | a |$，其中 $| s |$ 表示字符串 $s$ 的长度），使得对所有 $j < i$ 都有 $a_j = b_j$，且 $a_i < b_i$。输入的第一行包含字符串 $s$，它仅由字符 '_0_'、'_1_' 和 '_2_' 组成，其长度在 $1$ 到 $10^5$（含）之间。输出一个字符串——通过上述交换操作任意次（可能为零次）所能获得的字典序最小的字符串。 ## Input 输入的第一行包含字符串 $s$，它仅由字符 '_0_'、'_1_' 和 '_2_' 组成，其长度在 $1$ 到 $10^5$（含）之间。 ## Output 输出一个字符串——通过上述交换操作任意次（可能为零次）所能获得的字典序最小的字符串。 [samples]

**Definitions** Let $ s \in \{0,1,2\}^* $ be a ternary string. **Constraints** Allowed operations: - Swap adjacent $ 0 $ and $ 1 $: $ 01 \leftrightarrow 10 $ - Swap adjacent $ 1 $ and $ 2 $: $ 12 \leftrightarrow 21 $ - No swap between $ 0 $ and $ 2 $: $ 02 \not\leftrightarrow 20 $ **Objective** Find the lexicographically minimal string obtainable from $ s $ via any finite sequence of allowed adjacent swaps.

Samples

Input #1

Output #1

Input #2

11222121

Output #2

11112222

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Minimum Ternary String",
    "description": {
      "content": "You are given a ternary string (it is a string which consists only of characters '_0_', '_1_' and '_2_'). You can swap any two adjacent (consecutive) characters '_0_' and '_1_' (i.e. replace \"_01_\" w",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1009B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a ternary string (it is a string which consists only of characters '_0_', '_1_' and '_2_').\n\nYou can swap any two adjacent (consecutive) characters '_0_' and '_1_' (i.e. replace \"_01_\" w...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你一个三元字符串（即仅由字符 '_0_'、'_1_' 和 '_2_' 组成的字符串）。\n\n你可以交换任意两个相邻（连续）的字符 '_0_' 和 '_1_'（即用 \"_10_\" 替换 \"_01_\"，或反之亦然），或者交换任意两个相邻（连续）的字符 '_1_' 和 '_2_'（即用 \"_21_\" 替换 \"_12_\"，或反之亦然）。\n\n例如，对于字符串 \"_010210_\"，我们可以执行以下操作：\n\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{0,1,2\\}^* $ be a ternary string.\n\n**Constraints**  \nAllowed operations:  \n- Swap adjacent $ 0 $ and $ 1 $: $ 01 \\leftrightarrow 10 $  \n- Swap adjacent $ 1 $ and $ 2 $: ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments