当前没有测试数据。

USACO 2024 US Open Contest, Gold Problem 1: Cowreography

I. Problem Description

1. Dance Team Situation
   • The cows have formed a dance team, and Farmer John is their choreographer! The team's latest and greatest dance involves N cows ($2\leq N\leq10^{6}$) standing in a line.
   • There are two types of cows in the line – Guernseys and Holsteins. 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.
2. Dance Move Rules
   • Each move in the dance involves two cows, up to K positions apart ($1\leq K<N$), gracefully jumping and landing in each other's position.
3. Problem Scenario
   • 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!

II. Input Format

1. The first line contains N and K.
2. The second line contains the first binary string.
3. The third line contains the last binary string.
   • It is guaranteed that both binary strings contain the same number of ones.

III. Output Format

Output the minimum number of moves in the dance.

IV. Sample Input and Output

1. Sample 1
   • Input
     • 4 1
     • 0111
     • 1110
   • Output
     • 3
   • Explanation
     • One possible dance: 0111 -> 1011 -> 1101 -> 1110
2. Sample 2
   • Input
     • 5 2
     • 11000
     • 00011
   • Output
     • 3
   • Explanation
     • One possible dance: 11000 -> 01100 -> 00110 -> 00011
3. Sample 3
   • Input
     • 5 4
     • 11000
     • 00011
   • Output
     • 2
   • Explanation
     • One possible dance: 11000 -> 10010 -> 00011

V. Scoring Rules

1. Inputs 4 - 5: K = 1.
2. Inputs 6 - 7: Both strings have at most 8 ones.
3. Inputs 8 - 15: N≤5000.
4. Inputs 16 - 23: No additional constraints.

VI. Problem Source

Problem credits: Benjamin Qi. Contest has ended. No further submissions allowed.