← 返回题目列表

AtCoder · nomura2020_e

E. 二进制编程

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

分数: 900 点

问题陈述

Takahashi 有一个空字符串 S 和一个变量 x 其初始值为 0.

另外,我们有一个字符串 T 组成 0 和 1.

现在,高桥将执行以下两个步骤的操作 |T| 次。

  • 插入 0 或 1 在任意位置 S 他的选择。
  • 然后,递增 x 的奇数位置(第一、第三、第五……)的数字之和 S。例如,如果 S is 01101,奇数位置的数字是 0, 1, 1 从左到右,所以 x 增加 2.

打印最大可能的最终值 x 在一系列操作中,使得 S 等于 T 最后。

约束

  • 1 \leq |T| \leq 2 \times 10^5
  • T 包括 0 和 1.

输入

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

T

输出

打印最大可能的最终值 x 在一系列操作中,使得 S 等于 T 最后。


样本输入 1

1101

示例输出 1

5

下面是最大化最终值的一系列操作 x to 5.

  • 插入 1 开头 S. S 变为 1,和 x 增加 1.
  • 插入 0 位于第一个字符的右侧 S. S 变为 10,和 x 增加 1.
  • 插入 1 紧邻第二个字符的右侧 S. S 变为 101,和 x 增加 2.
  • 插入 1 开头 S. S 变为 1101,和 x 增加 1.

示例输入 2

0111101101

示例输出 2

26