B. Binary String Constructing

Codeforces

IDCF1003B

Time1000ms

Memory256MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

You are given three integers $a$, $b$ and $x$. Your task is to construct a binary string $s$ of length $n = a + b$ such that there are exactly $a$ zeroes, exactly $b$ ones and exactly $x$ indices $i$ (where $1 \le i < n$) such that $s_i \ne s_{i + 1}$. It is guaranteed that the answer always exists. For example, for the string "_01010_" there are four indices $i$ such that $1 \le i < n$ and $s_i \ne s_{i + 1}$ ($i = 1, 2, 3, 4$). For the string "_111001_" there are two such indices $i$ ($i = 3, 5$). Recall that binary string is a non-empty sequence of characters where each character is either _0_ or _1_. ## Input The first line of the input contains three integers $a$, $b$ and $x$ ($1 \le a, b \le 100, 1 \le x < a + b)$. ## Output Print only one string $s$, where $s$ is **any** binary string satisfying conditions described above. It is guaranteed that the answer always exists. [samples] ## Note All possible answers for the first example: * _1100_; * _0011_. All possible answers for the second example: * _110100_; * _101100_; * _110010_; * _100110_; * _011001_; * _001101_; * _010011_; * _001011_.

给你三个整数 $a$、$b$ 和 $x$。你的任务是构造一个长度为 $n = a + b$ 的二进制字符串 $s$，使得其中恰好有 $a$ 个零、恰好 $b$ 个一，并且恰好有 $x$ 个索引 $i$（其中 $1 lt.eq i < n$）满足 $s_i != s_{i + 1}$。题目保证答案一定存在。例如，对于字符串 "_01010_"，有四个索引 $i$ 满足 $1 lt.eq i < n$ 且 $s_i != s_{i + 1}$（$i = 1, 2, 3, 4$）。对于字符串 "_111001_"，有两个这样的索引 $i$（$i = 3, 5$）。回忆一下，二进制字符串是非空的字符序列，其中每个字符要么是 _0_，要么是 _1_。输入的第一行包含三个整数 $a$、$b$ 和 $x$（$1 lt.eq a, b lt.eq 100$，$1 lt.eq x < a + b$）。请仅输出一个字符串 $s$，其中 $s$ 是满足上述条件的任意一个二进制字符串。题目保证答案一定存在。第一个示例的所有可能答案：第二个示例的所有可能答案： ## Input 输入的第一行包含三个整数 $a$、$b$ 和 $x$（$1 lt.eq a, b lt.eq 100$，$1 lt.eq x < a + b$）。 ## Output 请仅输出一个字符串 $s$，其中 $s$ 是满足上述条件的任意一个二进制字符串。题目保证答案一定存在。 [samples] ## Note 第一个示例的所有可能答案： _1100_；_0011_。第二个示例的所有可能答案： _110100_；_101100_；_110010_；_100110_；_011001_；_001101_；_010011_；_001011_。

**Definitions** Let $ a, b, x \in \mathbb{Z}^+ $ such that $ 1 \leq a, b \leq 100 $ and $ 1 \leq x < a + b $. Let $ n = a + b $. Let $ s = s_1 s_2 \dots s_n $ be a binary string of length $ n $, where each $ s_i \in \{0, 1\} $. **Constraints** 1. The string $ s $ contains exactly $ a $ zeros and $ b $ ones. 2. The number of indices $ i \in \{1, 2, \dots, n-1\} $ such that $ s_i \neq s_{i+1} $ is exactly $ x $. **Objective** Construct any binary string $ s $ satisfying the above constraints.

Samples

Input #1

2 2 1

Output #1

Input #2

3 3 3

Output #2

Input #3

5 3 6

Output #3

01010100

API Response (JSON)

{
  "problem": {
    "name": "B. Binary String Constructing",
    "description": {
      "content": "You are given three integers $a$, $b$ and $x$. Your task is to construct a binary string $s$ of length $n = a + b$ such that there are exactly $a$ zeroes, exactly $b$ ones and exactly $x$ indices $i$ ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1003B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given three integers $a$, $b$ and $x$. Your task is to construct a binary string $s$ of length $n = a + b$ such that there are exactly $a$ zeroes, exactly $b$ ones and exactly $x$ indices $i$ ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你三个整数 $a$、$b$ 和 $x$。你的任务是构造一个长度为 $n = a + b$ 的二进制字符串 $s$，使得其中恰好有 $a$ 个零、恰好 $b$ 个一，并且恰好有 $x$ 个索引 $i$（其中 $1 lt.eq i < n$）满足 $s_i != s_{i + 1}$。题目保证答案一定存在。\n\n例如，对于字符串 \"_01010_\"，有四个索引 $i$ 满足 $1 lt.eq i < ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b, x \\in \\mathbb{Z}^+ $ such that $ 1 \\leq a, b \\leq 100 $ and $ 1 \\leq x < a + b $.  \nLet $ n = a + b $.  \nLet $ s = s_1 s_2 \\dots s_n $ be a binary string of length $ n $,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments