F. Restoring the Expression

Codeforces

IDCF898F

Time2000ms

Memory256MB

Difficulty—

brute forcehashingmath

English · Original

Chinese · Translation

Formal · Original

A correct expression of the form _a+b=c_ was written; _a_, _b_ and _c_ are non-negative integers without leading zeros. In this expression, the plus and equally signs were lost. The task is to restore the expression. In other words, one character '_+_' and one character '_\=_' should be inserted into given sequence of digits so that: * character'_+_' is placed on the left of character '_\=_', * characters '_+_' and '_\=_' split the sequence into three non-empty subsequences consisting of digits (let's call the left part _a_, the middle part — _b_ and the right part — _c_), * all the three parts _a_, _b_ and _c_ do not contain leading zeros, * it is true that _a+b=c_. It is guaranteed that in given tests answer always exists. ## Input The first line contains a non-empty string consisting of digits. The length of the string does not exceed 106. ## Output Output the restored expression. If there are several solutions, you can print any of them. Note that the answer **at first** should contain two terms (divided with symbol '_+_'), and then the result of their addition, before which symbol'_\=_' should be. Do not separate numbers and operation signs with spaces. Strictly follow the output format given in the examples. If you remove symbol '_+_' and symbol '_\=_' from answer string you should get a string, **same as** string from the input data. [samples]

一个形如 _a+b=c_ 的正确表达式被写下了；#cf_span[a]、#cf_span[b] 和 #cf_span[c] 是没有前导零的非负整数。在这个表达式中，加号和等号丢失了。任务是恢复该表达式。换句话说，需要在给定的数字序列中插入一个字符 '_+_' 和一个字符 '_=_'，使得：保证在给定的测试中答案总是存在。第一行包含一个由数字组成的非空字符串。字符串的长度不超过 #cf_span[106]。请输出恢复后的表达式。如果有多个解，可以输出任意一个。注意，答案 *首先* 应包含两个项（用符号 '_+_' 分隔），然后是它们的和，在其前应放置符号 '_=_'。不要在数字和运算符号之间添加空格。严格遵循示例中给出的输出格式。如果从答案字符串中移除符号 '_+_' 和 '_=_'，你应当得到一个与输入数据字符串 *完全相同* 的字符串。 ## Input 第一行包含一个由数字组成的非空字符串。字符串的长度不超过 #cf_span[106]。 ## Output 请输出恢复后的表达式。如果有多个解，可以输出任意一个。注意，答案 *首先* 应包含两个项（用符号 '_+_' 分隔），然后是它们的和，在其前应放置符号 '_=_'。不要在数字和运算符号之间添加空格。严格遵循示例中给出的输出格式。如果从答案字符串中移除符号 '_+_' 和 '_=_'，你应当得到一个与输入数据字符串 *完全相同* 的字符串。 [samples]

Let $ s \in \{0,1,\dots,9\}^* $ be the input string of digits, with $ 1 \leq |s| \leq 10^6 $. Find indices $ i, j \in \mathbb{Z} $ such that: - $ 1 \leq i < j \leq |s| $, - $ a = \text{int}(s[0:i]) $, - $ b = \text{int}(s[i:j]) $, - $ c = \text{int}(s[j:|s|]) $, - $ a + b = c $, - $ a, b, c $ have no leading zeros (i.e., if length > 1, first digit ≠ '0'). Output: $ a + b = c $ as a concatenated string.

Samples

Input #1

12345168

Output #1

123+45=168

Input #2

Output #2

0+9=9

Input #3

Output #3

1+99=100

Input #4

123123123456456456579579579

Output #4

123123123+456456456=579579579

API Response (JSON)

{
  "problem": {
    "name": "F. Restoring the Expression",
    "description": {
      "content": "A correct expression of the form _a+b=c_ was written; _a_, _b_ and _c_ are non-negative integers without leading zeros. In this expression, the plus and equally signs were lost. The task is to restore",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF898F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A correct expression of the form _a+b=c_ was written; _a_, _b_ and _c_ are non-negative integers without leading zeros. In this expression, the plus and equally signs were lost. The task is to restore...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一个形如 _a+b=c_ 的正确表达式被写下了；#cf_span[a]、#cf_span[b] 和 #cf_span[c] 是没有前导零的非负整数。在这个表达式中，加号和等号丢失了。任务是恢复该表达式。换句话说，需要在给定的数字序列中插入一个字符 '_+_' 和一个字符 '_=_'，使得：\n\n保证在给定的测试中答案总是存在。\n\n第一行包含一个由数字组成的非空字符串。字符串的长度不超过 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s \\in \\{0,1,\\dots,9\\}^* $ be the input string of digits, with $ 1 \\leq |s| \\leq 10^6 $.\n\nFind indices $ i, j \\in \\mathbb{Z} $ such that:\n- $ 1 \\leq i < j \\leq |s| $,\n- $ a = \\text{int}(s[0:i]) $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments