Cyanide Rivers
Time limit1sMemory limit1024 MB
Given a binary string whose first and last digits are 1, each 0 needs a neighboring tower certified at least one day earlier; find the minimum number of days to certify all towers.
- Level
Medium6 of 10
- Topics
- Greedy, Dynamic programming, String, Binary search
- Solved
- No attempts yet
Problem
Cyanide rivers flowing out from the Martian south polar ice cap are quite dangerous because of their toxic contents, and any activity in their close proximity is often extremely time consuming.
A row of communication towers was built in the area before the rivers even appeared after Martian global warming events.
Some of the towers now stand directly in a river, while others remain outside, on the river shores or on islands in the rivers. The first and the last tower in the row stand on river shores.
All towers are to be officially certified for the next operation period under the present difficult conditions.
The towers standing on the shore or on an island can be certified immediately. Access to the towers in rivers is hazardous and requires a lot of caution. Certifying a tower standing in a river takes one whole day. Moreover, a tower standing in a river can be certified only if at least one of its immediate neighbor towers has been certified at least one day earlier. Fortunately, the certification process can be performed independently on each tower, so it is possible to certify more than one tower in a day.
The certification process has to be completed as soon as possible.
Input
The input consists of one line containing an odd binary number with up to 300 000 digits and with no leading zeros. Each digit represents one tower. Towers standing in a river are represented by 0's, and the remaining towers are represented by 1's. The order of the digits is the same as the order of the towers in the row.
Output
Print the minimum number of whole days in which all towers can be certified.