← 返回题目列表

Codeforces · 92/B

B. 二进制数

中文机器翻译题面 查看原题

小海象Fangy非常喜欢数学。这就是为什么当他无聊的时候,他会玩一些执行一些操作的数字。

Fangy 取一些正整数 x 并想从中得到一个数字 1。当 x 不等于 1 时,Fangy 重复以下操作:如果 x 是奇数,则将其加 1,否则将 x 除以 2。Fangy 知道,对于任何正整数,该过程都会在有限时间内结束。

Fangy 应该执行多少个动作才能从数字 x 中获得第一?

输入

第一行包含一个二进制正整数 x。保证x的第一位不为0且位数不超过106。

输出

打印所需的操作数。

示例

输入 #1

1

输出 #1

0

输入 #2

1001001

输出 #2

12

输入 #3

101110

输出 #3

8

注意

让我们考虑第三个示例。数字 101110 是偶数,这意味着我们应该将它除以 2。除法后,Fangy 得到一个奇数 10111 并加一。数字 11000 可以连续除以 2 三次,得到数字 11。剩下的就是将数字加一(我们得到 100),然后连续除以 2 两次。结果,我们得到 1。