B. Binary Number

Codeforces

IDCF92B

Time1000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

Little walrus Fangy loves math very much. That's why when he is bored he plays with a number performing some operations. Fangy takes some positive integer _x_ and wants to get a number one from it. While _x_ is not equal to 1, Fangy repeats the following action: if _x_ is odd, then he adds 1 to it, otherwise he divides _x_ by 2. Fangy knows that for any positive integer number the process ends in finite time. How many actions should Fangy perform to get a number one from number _x_? ## Input The first line contains a positive integer _x_ in a **binary system**. It is guaranteed that the first digit of _x_ is different from a zero and the number of its digits does not exceed 106. ## Output Print the required number of actions. [samples] ## Note Let's consider the third sample. Number 101110 is even, which means that we should divide it by 2. After the dividing Fangy gets an odd number 10111 and adds one to it. Number 11000 can be divided by 2 three times in a row and get number 11. All that's left is to increase the number by one (we get 100), and then divide it by 2 two times in a row. As a result, we get 1.

小海象 Fangy 非常热爱数学。因此，当他无聊时，他会通过一些运算来玩数字。 Fangy 取一个正整数 #cf_span[x]，并希望将其变为数字 1。当 #cf_span[x] 不等于 #cf_span[1] 时，Fangy 重复以下操作：如果 #cf_span[x] 是奇数，则将其加 #cf_span[1]；否则，将 #cf_span[x] 除以 #cf_span[2]。Fangy 知道，对于任意正整数，该过程都会在有限步内结束。 Fangy 需要执行多少次操作才能从数字 #cf_span[x] 得到数字 1？第一行包含一个以 *二进制系统* 表示的正整数 #cf_span[x]。保证 #cf_span[x] 的首位数字不为零，且其位数不超过 #cf_span[106]。请输出所需的行动次数。考虑第三个样例。数字 #cf_span[101110] 是偶数，因此应将其除以 #cf_span[2]。除法后，Fangy 得到一个奇数 #cf_span[10111]，并将其加一。数字 #cf_span[11000] 可以连续除以 #cf_span[2] 三次，得到数字 #cf_span[11]。剩下的操作是将数字加一（得到 #cf_span[100]），然后连续除以 #cf_span[2] 两次。最终，我们得到 #cf_span[1]。 ## Input 第一行包含一个以 *二进制系统* 表示的正整数 #cf_span[x]。保证 #cf_span[x] 的首位数字不为零，且其位数不超过 #cf_span[106]。 ## Output 请输出所需的行动次数。 [samples] ## Note 考虑第三个样例。数字 #cf_span[101110] 是偶数，因此应将其除以 #cf_span[2]。除法后，Fangy 得到一个奇数 #cf_span[10111]，并将其加一。数字 #cf_span[11000] 可以连续除以 #cf_span[2] 三次，得到数字 #cf_span[11]。剩下的操作是将数字加一（得到 #cf_span[100]），然后连续除以 #cf_span[2] 两次。最终，我们得到 #cf_span[1]。

Let $ x $ be a positive integer given in binary representation. Define the function $ f: \mathbb{Z}^+ \to \mathbb{Z}^+ $ as: $$ f(n) = \begin{cases} n + 1 & \text{if } n \text{ is odd}, \\ n / 2 & \text{if } n \text{ is even}. \end{cases} $$ Let $ a_0 = x $, and for $ i \geq 0 $, define $ a_{i+1} = f(a_i) $. The process terminates when $ a_k = 1 $ for some $ k \in \mathbb{N} $. **Objective:** Find the smallest $ k $ such that $ a_k = 1 $. Given: $ x $ is provided as a binary string of length at most $ 10^6 $, with no leading zeros. Compute $ k $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Binary Number",
    "description": {
      "content": "Little walrus Fangy loves math very much. That's why when he is bored he plays with a number performing some operations. Fangy takes some positive integer _x_ and wants to get a number one from it. W",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF92B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Little walrus Fangy loves math very much. That's why when he is bored he plays with a number performing some operations.\n\nFangy takes some positive integer _x_ and wants to get a number one from it. W...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "小海象 Fangy 非常热爱数学。因此，当他无聊时，他会通过一些运算来玩数字。\n\nFangy 取一个正整数 #cf_span[x]，并希望将其变为数字 1。当 #cf_span[x] 不等于 #cf_span[1] 时，Fangy 重复以下操作：如果 #cf_span[x] 是奇数，则将其加 #cf_span[1]；否则，将 #cf_span[x] 除以 #cf_span[2]。Fangy 知道，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ x $ be a positive integer given in binary representation.\n\nDefine the function $ f: \\mathbb{Z}^+ \\to \\mathbb{Z}^+ $ as:\n$$\nf(n) =\n\\begin{cases}\nn + 1 & \\text{if } n \\text{ is odd}, \\\\\nn / 2 & \\t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments