A. Minimum Binary Number

Codeforces

IDCF976A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

String can be called _correct_ if it consists of characters "_0_" and "_1_" and there are no redundant leading zeroes. Here are some examples: "_0_", "_10_", "_1001_". You are given a _correct_ string _s_. You can perform two different operations on this string: 1. swap any pair of adjacent characters (for example, "_101_" "_110_"); 2. replace "_11_" with "_1_" (for example, "_110_" "_10_"). Let _val_(_s_) be such a number that _s_ is its binary representation. _Correct_ string _a_ is less than some other _correct_ string _b_ iff _val_(_a_) < _val_(_b_). Your task is to find the minimum _correct_ string that you can obtain from the given one using the operations described above. You can use these operations any number of times in any order (or even use no operations at all). ## Input The first line contains integer number _n_ (1 ≤ _n_ ≤ 100) — the length of string _s_. The second line contains the string _s_ consisting of characters "_0_" and "_1_". It is guaranteed that the string _s_ is _correct_. ## Output Print one string — the minimum _correct_ string that you can obtain from the given one. [samples] ## Note In the first example you can obtain the answer by the following sequence of operations: "_1001_" "_1010_" "_1100_" "_100_". In the second example you can't obtain smaller answer no matter what operations you use.

如果一个字符串仅由字符 "_0_" 和 "_1_" 组成，且没有多余的前导零，则称其为 _正确_ 字符串。例如："_0_"、"_10_"、"_1001_"。给定一个 _正确_ 字符串 #cf_span[s]。你可以对该字符串执行两种不同的操作：令 #cf_span[val(s)] 表示以 #cf_span[s] 为二进制表示的数值。 _正确_ 字符串 #cf_span[a] 小于另一个 _正确_ 字符串 #cf_span[b]，当且仅当 #cf_span[val(a) < val(b)]。你的任务是找出通过上述操作可以从给定字符串获得的最小 _正确_ 字符串。你可以任意次数、任意顺序使用这些操作（甚至可以选择不使用任何操作）。第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——字符串 #cf_span[s] 的长度。第二行包含由字符 "_0_" 和 "_1_" 组成的字符串 #cf_span[s]。保证字符串 #cf_span[s] 是 _正确_ 的。请输出一个字符串——你可以从给定字符串获得的最小 _正确_ 字符串。在第一个例子中，你可以通过以下操作序列获得答案："_1001_" → "_1010_" → "_1100_" → "_100_"。在第二个例子中，无论使用何种操作，都无法获得更小的答案。 ## Input 第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——字符串 #cf_span[s] 的长度。第二行包含由字符 "_0_" 和 "_1_" 组成的字符串 #cf_span[s]。保证字符串 #cf_span[s] 是 _正确_ 的。 ## Output 请输出一个字符串——你可以从给定字符串获得的最小 _正确_ 字符串。 [samples] ## Note 在第一个例子中，你可以通过以下操作序列获得答案："_1001_" → "_1010_" → "_1100_" → "_100_"。在第二个例子中，无论使用何种操作，都无法获得更小的答案。

**Definitions** Let $ s \in \{0,1\}^* $ be a correct binary string, i.e., $ s $ contains only characters '0' and '1', and has no leading zeros (so $ s = "0" $ or $ s[0] = '1' $). Let $ \text{val}(s) $ denote the integer value of $ s $ in binary representation. **Operations** You may perform any number of the following two operations on $ s $: 1. Swap any two adjacent characters. 2. Remove a leading '1' and append a '0' at the end (i.e., transform $ "1" + x $ into $ x + "0" $, provided $ x $ is a binary string and the result remains correct). **Constraints** 1. $ 1 \leq n \leq 100 $, where $ n = |s| $. 2. $ s $ is correct: $ s = "0" $ or $ s[0] = '1' $. **Objective** Find the lexicographically smallest correct string $ s' $ such that $ s' $ can be obtained from $ s $ via any sequence of the above operations.

Samples

Input #1

4
1001

Output #1

Input #2

1
1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Minimum Binary Number",
    "description": {
      "content": "String can be called _correct_ if it consists of characters \"_0_\" and \"_1_\" and there are no redundant leading zeroes. Here are some examples: \"_0_\", \"_10_\", \"_1001_\". You are given a _correct_ strin",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF976A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "String can be called _correct_ if it consists of characters \"_0_\" and \"_1_\" and there are no redundant leading zeroes. Here are some examples: \"_0_\", \"_10_\", \"_1001_\".\n\nYou are given a _correct_ strin...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "如果一个字符串仅由字符 \"_0_\" 和 \"_1_\" 组成，且没有多余的前导零，则称其为 _正确_ 字符串。例如：\"_0_\"、\"_10_\"、\"_1001_\"。\n\n给定一个 _正确_ 字符串 #cf_span[s]。\n\n你可以对该字符串执行两种不同的操作：\n\n令 #cf_span[val(s)] 表示以 #cf_span[s] 为二进制表示的数值。\n\n_正确_ 字符串 #cf_span[a] 小于另一...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{0,1\\}^* $ be a correct binary string, i.e., $ s $ contains only characters '0' and '1', and has no leading zeros (so $ s = \"0\" $ or $ s[0] = '1' $).  \nLet $ \\text{val}(...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments