п»ї
Коровы сформировали танцевальную команду, а Фермер Джон их хореограф.
Последний и самый большой танец включает \(N\) коров (\(2 \le N \le 10^6\)),
стоящих в ряд. Каждое движение в танце вовлекает две коровы на расстоянии
до \(K\) позиций друг от друга (\(1 \le K < N\)) грациозно прыгающих
и приземляющихся в каждой другой позиции.
�меется два типа коров в этом ряду Guernseys и Holsteins. Поэтому ФД
задокументировал танец как последовательность двоичных строк
длины \(N\) , где a \(0\) представляет Guernsey, a \(1\) представляет
Holstein, и вся строка представляет как коровы расположены в ряду.
К несчастью Фермер Нхой (хореограф команды соперников)
стёр все строки кроме первой и последней.
Поскольку скоро состоится соревнование, ФД должен, не теряя времени,
реконструировать танец.
Вам даны две двоичные строки, помогите ФД определить минимальное количество
движений в танце.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) Рё
\(K\).
Вторая строка содержит первую двоичную строку.
Третья строка содержит последнюю двоичную строку.
Гарантируется, что обе двоичные строки содержат одинаковое
количество единиц.
ФОРМАТ ВЫВОДА (на экран / stdout):
Минимальное количество движений в танце.
ПР�МЕРВВОДА:
4 1
0111
1110
ПР�МЕРВЫВОДА:
3
Один возможный танец:
0111 -> 1011 -> 1101 -> 1110
ПР�МЕРВВОДА:
5 2
11000
00011
ПР�МЕРВЫВОДА:
3
Один возможный танец:
11000 -> 01100 -> 00110 -> 00011
ПР�МЕРВВОДА:
5 4
11000
00011
ПР�МЕРВЫВОДА:
2
Один возможный танец:
11000 -> 10010 -> 00011
ОЦЕН�ВАН�Е:
- Тесты 4-5: \(K=1\)
- Тесты 6-7: Обе строки имеют не более чем \(8\) единиц.
- Тесты 8-15: \(N\le 5000\)
- Тесты 16-23: Нет дополнительных ограничений.
Problem credits: Benjamin Qi