Binary Programming

AtCoder

IDnomura2020_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

Input #2

0111101101

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Binary Programming",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "nomura2020_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi has an empty string $S$ and a variable $x$ whose initial value is $0$.\nAlso, we have a string $T$ consisting of `0` and `1`.\nNow, Takahashi will do the operation with the following two steps...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments