E - Binary Programming 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 900

問題文

高橋くんは、空文字列 S と、0 で初期化された変数 x を持っています。

また 0 および 1 のみからなる文字列 T があります。

高橋くんはこれから、以下の 2 ステップからなる操作を |T| 回繰り返します。

  • S の好きな位置に 0 または 1 を挿入する。
  • 次に、S の左から奇数番目に書かれた数字の総和を x に加算する。例えば現在 S01101 であるなら、S の左から奇数番目に書かれた数字は左から 0, 1, 1 なので、2x に加算する。

最終的に ST に一致するような操作列における、最終的な x の値の最大値を出力してください。

制約

  • 1 \leq |T| \leq 2 \times 10^5
  • T0 および 1 のみからなる。

入力

入力は以下の形式で標準入力から与えられる。

T

出力

最終的に ST に一致するような操作列における、最終的な x の値の最大値を出力せよ。


入力例 1

1101

出力例 1

5

例えば以下のような操作列が、最終的な x の値を 5 に最大化します。

  • S の先頭に 1 を挿入する。S1 になり、x1 を加算する。
  • S1 文字目の直後に 0 を挿入する。S10 になり、x1 を加算する。
  • S2 文字目の直後に 1 を挿入する。S101 になり、x2 を加算する。
  • S の先頭に 1 を挿入する。S1101 になり、x1 を加算する。

入力例 2

0111101101

出力例 2

26

Score : 900 points

Problem Statement

Takahashi has an empty string S and a variable x whose initial value is 0.

Also, we have a string T consisting of 0 and 1.

Now, Takahashi will do the operation with the following two steps |T| times.

  • Insert a 0 or a 1 at any position of S of his choice.
  • Then, increment x by the sum of the digits in the odd positions (first, third, fifth, ...) of S. For example, if S is 01101, the digits in the odd positions are 0, 1, 1 from left to right, so x is incremented by 2.

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Constraints

  • 1 \leq |T| \leq 2 \times 10^5
  • T consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

T

Output

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.


Sample Input 1

1101

Sample Output 1

5

Below is one sequence of operations that maximizes the final value of x to 5.

  • Insert a 1 at the beginning of S. S becomes 1, and x is incremented by 1.
  • Insert a 0 to the immediate right of the first character of S. S becomes 10, and x is incremented by 1.
  • Insert a 1 to the immediate right of the second character of S. S becomes 101, and x is incremented by 2.
  • Insert a 1 at the beginning of S. S becomes 1101, and x is incremented by 1.

Sample Input 2

0111101101

Sample Output 2

26