AtCoder 图片原名已被搁置;此后,原始图像取自英语原文,现已完整保存。

可复制的 PDF 提取文本
Gennady Korotkevich Contest 1
Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013
Problem B. Bits Are Dangerous
Input le: bad.in
Output le: bad.out
Time limit: 2 seconds
Memory limit: 256 megabytes
Do you think that escaping a dream is easy? This is not the case when the dream is about bits.
You've surely read too much about bit theory yesterday, but this doesn't matter now as the only
thing you want to do is to escape from the dream. You've probably found the best special string
incorrectly... or they've just cheated you. You still have a long string of bits in front of your closed
eyes.
Then you realize that you have an ability to change the leftmost bit of this string from 0 to 1 or
from 1 to 0. It takes you exactly four seconds, but you can!
Then you realize that you can also shift this string cyclically, one position to the left or one
position to the right. Either of the actions takes you a whopping total of seven seconds in this
strange dream.
Something tells you that those 1-bits in the string are what's keeping you in the dream. As this
might be true, you decide to turn the string into a string of all zeroes you know that you have
everything required for that.
But how much time would it take you if you acted optimally?
Input
The only line of the input le contains S (2 ≤|S| ≤2 · 105) the string consisting of zeroes and
ones.
Output
Output the sought minimum time you need to turn S into a string of all zeroes, in seconds.
Examples
bad.in bad.out
11001 33
01101010 58
1000110101 62
011010100011 94
0000 0
Note
In the rst test case, the optimal strategy is the following: change the leftmost bit to get 01001,
shift the string cyclically to the left to get 10010, change the leftmost bit to get 00010, shift the
string cyclically to the right to get 00001, shift the string cyclically to the right (again) to get
10000, and then change the leftmost bit to get 00000. Three changes and three cyclic shifts would
take you exactly 33 seconds.
Page 2 of 10