C. Hexadecimal's Numbers

Codeforces
IDCF9C
Time1000ms
Memory64MB
Difficulty
brute forceimplementationmath
English · Original
Chinese · Translation
Formal · Original
One beautiful July morning a terrible thing happened in Mainframe: a mean virus Megabyte somehow got access to the memory of his not less mean sister Hexadecimal. He loaded there a huge amount of _n_ different natural numbers from 1 to _n_ to obtain total control over her energy. But his plan failed. The reason for this was very simple: Hexadecimal didn't perceive any information, apart from numbers written in binary format. This means that if a number in a decimal representation contained characters apart from 0 and 1, it was not stored in the memory. Now Megabyte wants to know, how many numbers were loaded successfully. ## Input Input data contains the only number _n_ (1 ≤ _n_ ≤ 109). ## Output Output the only number — answer to the problem. [samples] ## Note For _n_ = 10 the answer includes numbers 1 and 10.
一个美丽的七月早晨,Mainframe 发生了一件可怕的事情:邪恶的病毒 Megabyte 以某种方式获得了他同样邪恶的姐姐 Hexadecimal 的内存访问权限。他将从 1 到 #cf_span[n] 的 #cf_span[n] 个不同的自然数加载到内存中,以完全控制她的能量。 但他的计划失败了。原因非常简单:Hexadecimal 仅能识别以二进制格式书写的数字。这意味着,如果一个十进制表示的数字包含除 0 和 1 以外的字符,则不会被存储在内存中。现在 Megabyte 想知道,有多少个数字成功被加载了。 输入数据包含一个数字 #cf_span[n](#cf_span[1 ≤ n ≤ 109])。 请输出一个数字——问题的答案。 当 #cf_span[n] = 10 时,答案包含数字 1 和 10。 ## Input 输入数据包含一个数字 #cf_span[n](#cf_span[1 ≤ n ≤ 109])。 ## Output 请输出一个数字——问题的答案。 [samples] ## Note 当 #cf_span[n] = 10 时,答案包含数字 1 和 10。
**Given:** $n \in \mathbb{Z}$ such that $1 \le n \le 10^9$. **Definitions:** Let $D_{10}(x)$ be the set of digits in the decimal (base-10) representation of a positive integer $x$. **Objective:** Compute the cardinality: $$ \left| \{ x \in \mathbb{Z} \mid 1 \le x \le n \land D_{10}(x) \subseteq \{0, 1\} \} \right| $$
Samples
Input #1
10
Output #1
2
API Response (JSON)
{
  "problem": {
    "name": "C. Hexadecimal's Numbers",
    "description": {
      "content": "One beautiful July morning a terrible thing happened in Mainframe: a mean virus Megabyte somehow got access to the memory of his not less mean sister Hexadecimal. He loaded there a huge amount of _n_ ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF9C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One beautiful July morning a terrible thing happened in Mainframe: a mean virus Megabyte somehow got access to the memory of his not less mean sister Hexadecimal. He loaded there a huge amount of _n_ ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一个美丽的七月早晨,Mainframe 发生了一件可怕的事情:邪恶的病毒 Megabyte 以某种方式获得了他同样邪恶的姐姐 Hexadecimal 的内存访问权限。他将从 1 到 #cf_span[n] 的 #cf_span[n] 个不同的自然数加载到内存中,以完全控制她的能量。\n\n但他的计划失败了。原因非常简单:Hexadecimal 仅能识别以二进制格式书写的数字。这意味着,如果一个十进制表...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Given:**\n$n \\in \\mathbb{Z}$ such that $1 \\le n \\le 10^9$.\n\n**Definitions:**\nLet $D_{10}(x)$ be the set of digits in the decimal (base-10) representation of a positive integer $x$.\n\n**Objective:**\nCo...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments