B. Lucky Numbers

Codeforces
IDCF95B
Time2000ms
Memory256MB
Difficulty
dpgreedy
English · Original
Chinese · Translation
Formal · Original
Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not. Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not. One day Petya came across a positive integer _n_. Help him to find the least super lucky number which is not less than _n_. ## Input The only line contains a positive integer _n_ (1 ≤ _n_ ≤ 10100000). This number doesn't have leading zeroes. ## Output Output the least super lucky number that is more than or equal to _n_. [samples]
Petya 喜欢幸运数字。众所周知,正整数如果其十进制表示中不包含除 #cf_span[4] 和 #cf_span[7] 以外的数字,则被称为 #cf_span(class=[tex-font-style-underline], body=[lucky])。例如,数字 #cf_span[47]、#cf_span[744]、#cf_span[4] 是幸运的,而 #cf_span[5]、#cf_span[17]、#cf_span[467] 则不是。 如果一个幸运数字的十进制表示中包含相等数量的 #cf_span[4] 和 #cf_span[7],则称其为 #cf_span(class=[tex-font-style-underline], body=[super lucky])。例如,数字 #cf_span[47]、#cf_span[7744]、#cf_span[474477] 是超级幸运的,而 #cf_span[4]、#cf_span[744]、#cf_span[467] 则不是。 有一天,Petya 遇到了一个正整数 #cf_span[n]。请帮他找出不小于 #cf_span[n] 的最小超级幸运数。 仅一行包含一个正整数 #cf_span[n](#cf_span[1 ≤ n ≤ 10100000])。该数没有前导零。 请输出不小于 #cf_span[n] 的最小超级幸运数。 ## Input 仅一行包含一个正整数 #cf_span[n](#cf_span[1 ≤ n ≤ 10100000])。该数没有前导零。 ## Output 请输出不小于 #cf_span[n] 的最小超级幸运数。 [samples]
**Definitions** Let $ S $ be the set of *super lucky* numbers: $$ S = \left\{ m \in \mathbb{Z}^+ \mid \text{decimal representation of } m \text{ contains only digits } 4 \text{ and } 7, \text{ and } \#_4(m) = \#_7(m) \right\} $$ where $ \#_d(m) $ denotes the count of digit $ d $ in the decimal representation of $ m $. **Constraints** Given $ n \in \mathbb{Z}^+ $, with $ 1 \leq n \leq 10^{100000} $, and $ n $ has no leading zeros. **Objective** Find $ \min \{ m \in S \mid m \geq n \} $.
Samples
Input #1
4500
Output #1
4747
Input #2
47
Output #2
47
API Response (JSON)
{
  "problem": {
    "name": "B. Lucky Numbers",
    "description": {
      "content": "Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF95B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 喜欢幸运数字。众所周知,正整数如果其十进制表示中不包含除 #cf_span[4] 和 #cf_span[7] 以外的数字,则被称为 #cf_span(class=[tex-font-style-underline], body=[lucky])。例如,数字 #cf_span[47]、#cf_span[744]、#cf_span[4] 是幸运的,而 #cf_span[5]、#cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S $ be the set of *super lucky* numbers:  \n$$ S = \\left\\{ m \\in \\mathbb{Z}^+ \\mid \\text{decimal representation of } m \\text{ contains only digits } 4 \\text{ and } 7, \\text{ and...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments