← 返回题目列表

Codeforces · 279/E

E. 美丽分解

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

Valera 认为一个数字是美丽的,如果它对于某个整数 k (k ≥ 0) 等于 2k 或 -2k 。最近,数学老师要求 Valera 将数字 n 表示为美丽数字的总和。由于瓦莱拉真的很贪心,他想用尽可能少的漂亮数字来完成任务。

帮助 Valera 找出他需要多少个数字。换句话说,如果将数字 n 分解为漂亮的被加数,则需要找到被加数最少的分解的大小。

输入

第一行包含字符串 s (1 ≤ |s| ≤ 106),即数字 n 的二进制表示形式,不带前导零 (n > 0)。

输出

打印一个整数——总共为 n 的漂亮数字的最小数量。

示例

输入 #1

10

输出 #1

1

输入 #2

111

输出 #2

2

输入 #3

1101101

输出 #3

4

注意

在第一个样本中,n = 2 是一个漂亮的数字。

在第二个样本中,n = 7,Valera 可以将其分解为和 23 + ( - 20)。

在第三个样本中,n = 109 可以分解为四个被加数之和,如下所示:27 + ( - 24) + ( - 22) + 20。