TopCoder

User's AC Ratio

100.0% (11/11)

Submission's AC Ratio

55.1% (27/49)

Description


憨明碼(Hammming Code)是一種你精心研發,全新的偵錯與更正技術!

透過憨明碼,我們可以找到從遠方傳送過來的資料找出要如何更正資料。

現在你得到了一串二進位資料,但你覺得這資料可能有點問題,

所以你透過憨明碼得知了正確的資料應該為何,因此想要把它更正

雖然你很強,但你的機器卻很弱,只能將目前的資料中連續 m 個位元反轉

而每次操作都會耗費你家的電力,所以你希望能操作越少次越好!

Input Format

本題只有一組測試資料:

第一行有兩個數字n,m,代表資料共有 n 個位元,一次能反轉連續 m 個位元 (1 <= m <= n <=106)

第二行有一個二進位資料,共 n 位,代表你原始收到的資料。

第三行有一個二進位資料,共 n 位,代表你經過憨明碼所得到的正確資訊。

Output Format

輸出一個數字 k ,代表最少需要經過 k 次操作才能從原始狀態改變為正確的資料。
如果不行達成的話,請輸出"No Way!!"。( 不含雙引號 )

Sample Input

2 2
11
00

Sample Output

1

Hints

Problem Source

原TIOJ1464 / 建中校內培訓第四次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 7000 65536 65536
1 7000 65536 65536
2 7000 65536 65536
3 7000 65536 65536
4 7000 65536 65536
5 7000 65536 65536
6 7000 65536 65536
7 7000 65536 65536
8 7000 65536 65536
9 7000 65536 65536
10 7000 65536 65536