JDCC '16 Contest 3 P3 - Letter Swap

View as PDF

Submit solution


Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Four year old Suzie was ecstatic to receive a large set of magnetic 0s and 1s for Christmas. She now spends most of her time using the letters to write out binary numbers on the kitchen fridge. Her most recent challenge has been to write out a number and then write it in reverse.

However, being a four year old, Suzie does not have a long reach. The only way she is able to change the number is to swap two adjacent bits. As an aspiring programmer and lazy child, she would like to make as few swaps as possible in order to reverse the number. Can you help Suzie figure out the fewest number of swaps she'll need to make?

Input

Each test case contains one number written in binary.

For 40\% of the cases, the length of the number will not exceed 100.

For the remaining cases, the length of the number will not exceed 100 000.

Output

Output the minimum number of swaps that Suzie has to make to reverse the number.

Sample Input

10110

Sample Output

2

Sample Input

101100010110010

Sample Output

10

Explanation for Sample Output

In the first case, Suzie only needs to swap the first and second bit, obtaining 01110, and then the last two bits, obtaining 01101.


Comments

There are no comments at the moment.