Monotone SE Min

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2195
64-bit integer IO format: %I64d      Java class name: Main

Description

Given a sequence of bits (0's and 1's), we want to find an arbitrary monotonically increasing curve (单调递增函数)that best fits the bits. That is, the i-th bit is b(i), and we want to find some curve, f, such that for x<y, f(x) <= f(y), and the sum over i of (f(i)-b(i))^2 (the squared error)(方差) is minimized. Given the sequence of bits as a string, return the minimum possible squared error.

Input

Multiple test cases!
For each case the input contains a string consisting of only 0 and 1 in one line. The bits string will contain between 1 and 200 elements.

Output

For each case, output the minimum possible squared error in one line, accurate up to 3 decimal places.

Sample Input

00
101

Sample Output

0.000
0.500

Hint: For example 1, we can make f(1) = 0,   f(2) = 0.
      For example 2, we can make f(1) = 0.5, f(2) = 0.5, f(3) = 1.
Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .