Bishwock
Contest: Codeforces Round 491 (Div. 2)
Difficulty rating: 1500
Tags: dp, greedy

Bishwock is a chess figure that consists of three squares resembling an "L-bar". This figure can be rotated by 90, 180 and 270 degrees so it can have four possible states:

XX   XX   .X   X.X.   .X   XX   XX

Bishwocks don't attack any squares and can even occupy on the adjacent squares as long as they don't occupy the same square.

Vasya has a board with $$$2\times n$$$ squares onto which he wants to put some bishwocks. To his dismay, several squares on this board are already occupied by pawns and Vasya can't put bishwocks there. However, pawns also don't attack bishwocks and they can occupy adjacent squares peacefully.

Knowing the positions of pawns on the board, help Vasya to determine the maximum amount of bishwocks he can put onto the board so that they wouldn't occupy the same squares and wouldn't occupy squares with pawns.

Input format:
The input contains two nonempty strings that describe Vasya's board. Those strings contain only symbols "0" (zero) that denote the empty squares and symbols "X" (uppercase English letter) that denote the squares occupied by pawns. Strings are nonempty and are of the same length that does not exceed $$$100$$$.

Output format:
Output a single integer — the maximum amount of bishwocks that can be placed onto the given board.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
00
00

Example output:
1

Example input:
00X00X0XXX0
0XXX0X00X00

Example output:
4

Editorial:
В этой задаче применим следующий жадный алгоритм. Будем идти по столбцам слева-направо, если мы сейчас рассматриваем столбец $$$i$$$ и мы можем поставить фигуру, занимающую клетки столбцов $$$i$$$ и $$$i+1$$$, то нужно ее поставить. Действительно, если в оптимальном решении столбец $$$i$$$ не занят ни одной фигурой, то в столбце $$$i+1$$$ клетки заняты максимум одним слонопотамом. Значит, его можно убрать и поставить в столбцы $$$i$$$ и $$$i+1$$$, от этого ответ станет не хуже.
Немного более сложный вопрос — как именно поставить фигуру, если все 4 клетки столбцов $$$i$$$ и $$$i+1$$$ свободны (в других случаях фигуру можно поставить только одним способом)? Разумеется, в столбце $$$i$$$ выгодно занять обе клетки. Оказывается, при этом неважно, какую именно клетку столбца $$$i+1$$$ займет слонопотам. Действительно, клетки столбца $$$i+1$$$ могут пригодиться только при размещении фигуры в столбцах $$$i+1$$$,$$$i+2$$$. Если в столбце $$$i+2$$$ свободно не более одной клетки, то разместить фигуру не получится и клетки столбца $$$i+1$$$ ни на что не влияют. Если же в столбце $$$i+2$$$ свободны обе клетки, то мы можем разместить слонопотама при любом выборе занятой клетки столбца $$$i+1$$$.
Из этого следует, что нам вообще можно не расставлять фигуры, а лишь пересчитывать количество свободных клеток в столбцах. В соответствии с описанным алгоритмом, получаем такой код. (см. D_1.cpp)
Более того, эту реализацию можно заметно упростить, сведя решение к двум случаям. (см. D_2.cpp).
Формально данную реализацию можно отнести к динамическому программированию. Разумеется, ее можно написать и не обладая глубокими знаниями этого метода.
Кроме того, задачу можно решать более "явной" динамикой (например в качестве состояния использовать номер текущего столбца и состояние предыдущего). В этом случае реализация будет чуть более сложной, но не будет необходимости доказывать описанные выше утверждения.