← 返回题目列表

AtCoder · jag2018summer_day2_e

E. 独立

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

分数: 100 点

问题陈述

Ao 喜欢某些非负整数集。

让 X 是一组非负整数。 不管她爱不爱 X 是否确定如下:

  • If X 是空集,她喜欢 X.
  • 如果对于任意(可能相同)两个元素 u 和 v in X,至少其中之一 u+v 和 {\rm abs}(u-v) 包含在 X,她喜欢 X.
  • 如果以上条件都不满足,她就不爱 X.

你是Ao的忠实粉丝,并且要向她展示一组非负整数。 目前你有一套 A 非负整数。 您想要从中删除(可能为零)元素 A 所以她喜欢剩下的整数集。 您还希望最大化剩余整数的数量。 剩下的最大整数是多少?

约束

  • A 不为空。
  • 中最大的元素 A 不大于 500,000

输入

输入由标准输入按以下格式给出:

S

在这里, S=S_0S_1...S_{|S|-1} 是表示的字符串 A。 对于每个 i ( 0 \leq i \leq |S|-1 ), S_i = 1 if A 包含 i 和 S_i = 0 如果没有。 可以保证 S_{|S|-1} is 1.

输出

打印剩余整数的最大数量。


示例输入 1

1000001001011

示例输出 1

3

套装 A = \{0,6,9,11,12\}。 如果你删除 9 和 11,Ao 喜欢剩余整数的集合: \{0,6,12\}.


示例输入 2

10110110101

示例输出 2

4

示例输入 3

0111

示例输出 3

0

剩余整数集必须为空。