mokoto's blog

By mokoto, history, 5 years ago, In English

You are given a strings of 0 and 1's. Now the task is to make the string consisting of only 1's. But you are allowed to perform only the following operation:

Take exactly k consecutive elements of string and change 1 to 0 and 0 to 1. Each operation takes 1 unit time so you have to determine the minimum time required to make the string of 1's only. If not possible return -1.

2 ≤ length of S ≤ 1000

Examples

Input

S = 00010110 k = 3

Output

3

Explanation

You can get 1 by first changing the leftmost 3 elements, getting to 11110110, then the rightmost 3, getting to 11110001, and finally the 3 left out 0's to 11111111; In 3 unit time.

Any approaches for it.

  • Vote: I like it
  • -5
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Yeah, it works. it cant be anything else than a minimum number. We can only just invert k symbols. It is true answer.

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This is a problem from Google Code Jam's 2017 Qualification round. Here's the link to the editorial: https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=0