Рассмотрим коридор, которой может быть представлен как матрица из $$$2$$$ строк и $$$n$$$ столбцов. Определим ячейку на пересечении $$$i$$$-й строки и $$$j$$$-го столбца как $$$(i, j)$$$. Расстояние между ячейками $$$(i_1, j_1)$$$ и $$$(i_2, j_2)$$$ равно $$$|i_1 - i_2| + |j_1 - j_2|$$$.
В клетке $$$(1, 1)$$$ стоит робот-пылесос. Некоторые клетки коридора чистые, остальные — грязные (клетка, в которой стоит робот, чистая). Вы хотите очистить коридор, поэтому вы планируете запустить робота для этой работы.
После запуска робот делает следующее. Пока есть хотя бы одна грязная клетка, робот выбирает ближайшую (к текущей клетке) клетку среди грязных, перемещается туда и очищает ее (клетка перестает быть грязной). После очистки робот снова находит ближайшую к его текущей клетке грязную клетку, и так далее. Этот процесс повторяется, пока весь коридор не станет чистым.
Однако в программе робота есть серьезная ошибка. Если в какой-то момент есть несколько ближайших (к текущей позиции робота) грязных клеток, то робот ломается.
Вы хотите сами очистить коридор так, чтобы робот не сломался. До запуска робота вы можете очистить несколько (возможно, ноль) грязных клеток вручную. Однако вы не хотите делать много грязной работы сами, когда у вас есть такой замечательный, умный (хоть и неправильно запрограммированный) робот, чтобы это делать. Обратите внимание, что вы не можете сделать чистую клетку грязной.
Посчитайте максимальное количество клеток, которые можно оставить грязными до запуска робота так, чтобы он не сломался.
В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество столбцов в коридоре.
Затем следуют две строки, означающие $$$1$$$-ю и $$$2$$$-ю строку коридора. В этих строках по $$$n$$$ символов, где 0 означает чистую клетку, а 1 означает грязную клетку. Стартовая клетка робота $$$(1, 1)$$$ чистая.
Выведите одно целое число — максимально возможное количество клеток, которые можно оставить грязными, до запуска робота так, чтобы он не сломался.
2 01 11
2
2 01 01
2
4 0101 1011
4
4 0000 0000
0
5 00011 10101
4
6 011111 111111
8
10 0101001010 1010100110
6
В первом примере можно очистить клетку $$$(1, 2)$$$, так что путь робота — $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$.
Во втором примере можно оставить коридор как есть, так что путь робота — $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$$$.
В третьем примере можно очистить клетку $$$(1, 2)$$$, так что путь робота — $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$$$.
В четвертом примере коридор уже чистый. Может, вы уже запускали робота?
Название |
---|