TopCoder SRM 589 - 900: FlippingBitsDiv1

Problem Statement

题意简述：

给出一个只包含字符'0'和字符'1'的字符串和数字 M。

允许两种操作：

1.将字符串的某一位取反。
2.将字符串的前 k * M 位全都取反。

设该字符串长度为N，
要求在只用这两种操作的情况下，
用最少的操作次数使得这个字符串的前 N-M 位构成的字符串和后 N-M 位构成的字符串完全相同。

字符串通过输入它的各个部分的方式给出，要求输出最少的操作次数。

保证字符串的长度小于或等于 300。

Goose Tattarrattat has a sequence B of bits. The length of the sequence is N. Tattarrattat also has a favorite integer M which is between 1 and N, inclusive.

A sequence of N bits is called a rotator sequence if it has the following property: its prefix of length N-M is equal to its suffix of length N-M.

For example, let M=2. Consider the sequence B="10101010". Its length is N=8, so we have N-M=6. The prefix of length 6 is "101010", the suffix of length 6 is "101010". They are the same, so this B is a rotator sequence. Now consider B="11010100". For this B we compare the prefix "110101" to the suffix "010100". They differ, so this B is not a rotator sequence.

Tattarrattat wants to change her sequence B into some rotator sequence. She will produce such a sequence in a sequence of steps. In each step she can do one of the following two types of changes to the sequence:

Flip any bit (from 1 to 0 or from 0 to 1).
Flip the first k*M bits, for any positive integer k.

You are given a String[] S and the int M. Concatenate all elements of S to obtain one long String. This String will represent the sequence B: each of its characters will be either '0' or '1'. Return the minimal number of steps required to obtain some rotator sequence.

Test cases

input
- S { "00111000" }
- M 1
output
Returns 2

note

An optimal solution: she can flip the first 2*1 bits to obtain "11111000", and then flip the first 5*1 bits to obtain "00000000" which is a rotator sequence.
input
- S { "101100001101" }
- M 3
output
Returns 2
input
- S { "11111111" }
- M 4
output
Returns 0
input
- S { "1101001000" }
- M 8
output
Returns 1
input
- S { "1", "10", "11", "100", "101", "110" }
- M 5
output
Returns 4

note

Don't forget to concatenate the elements of S.
input
- S { "1001011000101010001111111110111011011100110001001" }
- M 2
output
Returns 16

back to the menu

SRM 589 1 900 FlippingBitsDiv1

Problem Statement

Definition

Limits

Constraints

Test cases