J. Jumbled String

Codeforces

IDCF10193J

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Recall that a #cf_span(class=[tex-font-style-underline], body=[subsequence]) of a string is any string obtained by removing some subset of characters from the string, for instance "string", "sing", "i" and "sg" are all subsequences of "string". If the same subsequence can be obtained in exactly $t$ different ways, by removing different subsets of characters, we say that the subsequence occurs $t$ times. Jingfei wants to create a nonempty bit string that has the following properties: The input consists of a single line with four integers $a$, $b$, $c$, and $d$ ($0 <= a, b, c, d <= 10^9$). Output a bit string that satisfies the given requirements. If there are several solutions, output any one of them. If there are no solutions, output "_impossible_". ## Input The input consists of a single line with four integers $a$, $b$, $c$, and $d$ ($0 <= a, b, c, d <= 10^9$). ## Output Output a bit string that satisfies the given requirements. If there are several solutions, output any one of them. If there are no solutions, output "_impossible_". [samples]

**Definitions** Let $ s \in \{0,1\}^+ $ be a nonempty bit string. For any substring $ w \in \{0,1\}^* $, let $ f_s(w) $ denote the number of distinct ways to obtain $ w $ as a subsequence of $ s $. **Constraints** Given integers $ a, b, c, d \in \mathbb{Z}_{\geq 0} $ with $ 0 \leq a, b, c, d \leq 10^9 $, require: - $ f_s("0") = a $, - $ f_s("1") = b $, - $ f_s("01") = c $, - $ f_s("00") = d $. **Objective** Find a nonempty bit string $ s $ satisfying the above, or output "impossible" if no such string exists.

API Response (JSON)

{
  "problem": {
    "name": "J. Jumbled String",
    "description": {
      "content": "Recall that a #cf_span(class=[tex-font-style-underline], body=[subsequence]) of a string is any string obtained by removing some subset of characters from the string, for instance \"string\", \"sing\", \"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": "CF10193J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Recall that a #cf_span(class=[tex-font-style-underline], body=[subsequence]) of a string is any string obtained by removing some subset of characters from the string, for instance \"string\", \"sing\", \"i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{0,1\\}^+ $ be a nonempty bit string.  \nFor any substring $ w \\in \\{0,1\\}^* $, let $ f_s(w) $ denote the number of distinct ways to obtain $ w $ as a subsequence of $ s $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments