gold_Cowreography (USACO US_Open_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: greedy

The cows have formed a dance team, and Farmer John is their choreographer! The
team's latest and greatest dance involves $N$ cows ($2 \le N \le 10^6$) standing
in a line. Each move in the dance involves two cows, up to $K$ positions apart
($1 \le K < N$), gracefully jumping and landing in each other's position.
There are two types of cows in the line – Guernseys and Holsteins. As such,
Farmer John has documented the dance as a sequence of
length-$N$ binary
strings
, where a $0$ represents a Guernsey, a $1$ represents a Holstein, and
the overall string represents how the cows are arranged in the line.
Unfortunately, Farmer Nhoj (who choreographs for a rival team) has sabotaged the
dance and erased all but the first and last binary strings! With a big
competition quickly approaching, Farmer John must waste no time in
reconstructing the dance.
Given these two binary strings, help Farmer John find the minimum number of
moves in the dance!
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $N$ and $K$.
The second line contains the first binary string.
The third line contains the last binary string.
It is guaranteed that both binary strings contain the same number of ones.
OUTPUT FORMAT (print output to the terminal / stdout):
The minimum number of moves in the dance.
SAMPLE INPUT:
4 1
0111
1110
SAMPLE OUTPUT:
3
One possible dance:
0111 -> 1011 -> 1101 -> 1110
SAMPLE INPUT:
5 2
11000
00011
SAMPLE OUTPUT:
3
One possible dance:
11000 -> 01100 -> 00110 -> 00011
SAMPLE INPUT:
5 4
11000
00011
SAMPLE OUTPUT:
2
One possible dance:
11000 -> 10010 -> 00011
SCORING:
Inputs 4-5: $K=1$
Inputs 6-7: Both strings have at most $8$ ones.
Inputs 8-15: $N\le 5000$
Inputs 16-23: No additional constraints.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: