TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (21/21)

Submission's AC Ratio

54.0% (47/87)

Tags

Description


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

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

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

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

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

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

Input Format

本題只有一組測試資料:

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

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

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

Output Format

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

Sample Input 1

2 2
11
00

Sample Output 1

1

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 7000 65536 262144 1
1 7000 65536 262144 2
2 7000 65536 262144 3
3 7000 65536 262144 4
4 7000 65536 262144 5
5 7000 65536 262144 6
6 7000 65536 262144 7
7 7000 65536 262144 8
8 7000 65536 262144 9
9 7000 65536 262144 10
10 7000 65536 262144 11