{"problem":{"name":"D. Bishwock","description":{"content":"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: <center> XX   XX   .X   X.","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF991D"},"statements":[{"statement_type":"Markdown","content":"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:\n\n<center>\n\nXX   XX   .X   X.\nX.   .X   XX   XX\n\n</center>Bishwocks don't attack any squares and can even occupy on the adjacent squares as long as they don't occupy the same square.\n\nVasya 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.\n\nKnowing 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.\n\n## Input\n\nThe 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$.\n\n## Output\n\nOutput a single integer — the maximum amount of bishwocks that can be placed onto the given board.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Bishwock 是一种由三个方格组成的象棋棋子，形状类似一个 \"L-形条\"。该棋子可以旋转 90、180 和 270 度，因此共有四种可能的状态：\n\nBishwock 不攻击任何方格，即使它们占据相邻的方格也没有问题，只要不占据同一个方格即可。\n\nVasya 有一个 $2 \\times n$ 的棋盘，他希望在上面放置一些 bishwocks。令他失望的是，棋盘上某些方格已经被兵占据，Vasya 无法在这些方格上放置 bishwocks。然而，兵也不会攻击 bishwocks，它们可以和平地占据相邻的方格。\n\n已知棋盘上兵的位置，请帮助 Vasya 确定最多能放置多少个 bishwocks，使得它们不占据同一个方格，也不占据有兵的方格。\n\n输入包含两个非空字符串，描述 Vasya 的棋盘。这些字符串仅包含符号 \"_0_\"（零）表示空方格，以及符号 \"_X_\"（大写英文字母）表示被兵占据的方格。字符串非空且长度相同，长度不超过 $100$。\n\n请输出一个整数——在给定棋盘上最多能放置的 bishwocks 数量。\n\n## Input\n\nThe 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$.\n\n## Output\n\nOutput a single integer — the maximum amount of bishwocks that can be placed onto the given board.\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let the board be represented as two rows of length $ n $, with each cell either empty (`'0'`) or occupied by a pawn (`'X'`).  \nA bishwock is an L-shaped tromino covering exactly three cells, and may be placed in any of four rotations:\n\n- Type A: covers $(0, i), (0, i+1), (1, i)$  \n- Type B: covers $(0, i), (1, i), (1, i+1)$  \n- Type C: covers $(0, i+1), (1, i), (1, i+1)$  \n- Type D: covers $(0, i), (0, i+1), (1, i+1)$  \n\nfor $ i \\in \\{0, 1, \\dots, n-2\\} $.\n\nEach bishwock must be placed such that all three of its cells are **empty** (i.e., not occupied by pawns).  \nBishwocks may not overlap and may not cover pawn-occupied squares.\n\nDefine:\n- $ S_0, S_1 \\in \\{0, X\\}^n $: the two rows of the board.\n- $ \\mathcal{P} \\subseteq \\{0,1\\} \\times \\{0, \\dots, n-1\\} $: set of pawn-occupied positions.\n\nWe wish to find the maximum number of non-overlapping bishwocks that can be placed on empty cells.\n\nThis is a dynamic programming problem over columns.\n\nLet $ dp[i][mask] $ be the maximum number of bishwocks that can be placed in columns $ 0 $ through $ i-1 $, where $ mask \\in \\{0,1,2,3\\} $ encodes the occupancy status of the two cells in column $ i $:\n- mask = 0: both cells (row0, row1) in column $ i $ are free (not covered by any bishwock extending from left)\n- mask = 1: row0 occupied, row1 free\n- mask = 2: row0 free, row1 occupied\n- mask = 3: both occupied\n\nBut note: bishwocks span two columns. So we consider state transitions from column $ i $ to $ i+1 $, checking which bishwocks can be placed ending at or starting at column $ i $.\n\nAlternatively, define state $ dp[i][a][b] $: maximum bishwocks placed up to column $ i $, with $ a, b \\in \\{0,1\\} $ indicating whether cell $ (0,i) $ and $ (1,i) $ are **covered** by a bishwock that started at column $ i-1 $ (i.e., are already used and thus unavailable for new bishwocks starting at $ i $).\n\nBut since bishwocks span two columns, it’s better to process two columns at a time.\n\nStandard approach for tiling problems:\n\nLet $ dp[i] $ be the maximum number of bishwocks that can be placed in columns $ 0 $ to $ i-1 $, assuming that columns $ 0 $ to $ i-1 $ are completely filled (no overhangs).  \nBut since bishwocks can leave partial coverage, we need state to represent the occupancy of the **current column** due to bishwocks extending from the left.\n\nActually, since each bishwock covers two consecutive columns, define:\n\nLet $ dp[i][s] $ = maximum number of bishwocks placed in columns $ 0 $ to $ i $, where $ s \\in \\{0,1,2,3\\} $ is a bitmask representing which cells in column $ i $ are already covered by a bishwock that started at column $ i-1 $.\n\nBut more cleanly:\n\nWe process column by column. At column $ i $, we consider placing bishwocks that start at column $ i $, which will cover column $ i $ and $ i+1 $. So we need to know the state of column $ i $ (which cells are free) and column $ i+1 $.\n\nActually, standard solution for this known problem (CodeForces \"Bishwock\") uses DP with state $ dp[i][mask] $, where $ mask $ is a 2-bit mask representing which cells in column $ i $ are already occupied (by a bishwock placed earlier). But since bishwocks extend to the right, we consider placing them starting at column $ i $, and the state is the occupancy of column $ i $ **before** placing any bishwock starting at $ i $.\n\n**Formal DP Definition:**\n\nLet $ dp[i][s] $ = maximum number of bishwocks that can be placed in columns $ 0 $ to $ i-1 $, with the state $ s \\in \\{0,1,2,3\\} $ representing the occupancy status of column $ i $ **due to bishwocks placed in previous columns** (i.e., from column $ i-1 $).  \n- $ s = 0 $: both cells in column $ i $ are free  \n- $ s = 1 $: top cell occupied, bottom free  \n- $ s = 2 $: top free, bottom occupied  \n- $ s = 3 $: both occupied  \n\nBut note: bishwocks placed starting at column $ i-1 $ may have covered column $ i $, so at column $ i $, we know which cells are already taken.\n\nHowever, the board has pawns, so we must also check that no bishwock is placed on a pawn.\n\nLet $ board[0][i] $, $ board[1][i] \\in \\{0, X\\} $ be the input.\n\nDefine $ \\text{free}[r][i] = 1 $ if $ board[r][i] = '0' $, else 0.\n\nAt column $ i $, the available free cells are those that are both:\n- not occupied by a pawn, and\n- not already covered by a bishwock from the left (as encoded in state $ s $).\n\nSo the **available** cells at column $ i $ are:\n- $ a_0 = \\text{free}[0][i] \\land (s \\& 1 == 0) $  // top cell available\n- $ a_1 = \\text{free}[1][i] \\land (s \\& 2 == 0) $  // bottom cell available\n\nWe now consider placing zero or more bishwocks starting at column $ i $. Since each bishwock spans two columns, we look at column $ i $ and $ i+1 $.\n\nWe try all possible bishwock placements starting at column $ i $ that cover three of the six cells: (0,i), (1,i), (0,i+1), (1,i+1), under the constraint that:\n- The three cells covered are all available (free and not already covered),\n- And the placement is one of the four valid L-shapes.\n\nThen we update the state for column $ i+1 $.\n\nThe four possible bishwocks starting at column $ i $:\n\n1. **Type A**: covers (0,i), (0,i+1), (1,i)  \n   → requires: a0, free[0][i+1], a1  \n   → leaves column $ i+1 $ with bottom cell covered → state = 2\n\n2. **Type B**: covers (0,i), (1,i), (1,i+1)  \n   → requires: a0, a1, free[1][i+1]  \n   → leaves column $ i+1 $ with top cell covered → state = 1\n\n3. **Type C**: covers (0,i+1), (1,i), (1,i+1)  \n   → requires: free[0][i+1], a1, free[1][i+1]  \n   → leaves column $ i+1 $ with top cell covered → state = 1\n\n4. **Type D**: covers (0,i), (0,i+1), (1,i+1)  \n   → requires: a0, free[0][i+1], free[1][i+1]  \n   → leaves column $ i+1 $ with bottom cell covered → state = 2\n\nAlso, we can place **no** bishwock at column $ i $, then state for column $ i+1 $ is 0, provided that column $ i $ is fully cleared (but we don’t need to clear it — we just move on).\n\nActually, since we are at column $ i $, and state $ s $ tells us what’s already covered from the left, we must ensure that after placing bishwocks starting at $ i $, the entire column $ i $ is covered (either by prior bishwocks or new ones). But we are allowed to leave column $ i $ with some cells uncovered if they are blocked by pawns? No — we can leave free cells uncovered, but we cannot place a bishwock on a pawn.\n\nImportant: We are not required to cover all free cells. We want to maximize the number of bishwocks.\n\nSo we can leave free cells empty. Therefore, we do **not** require that column $ i $ becomes fully covered. We just place as many bishwocks as possible, and the state $ s $ only encodes **which cells in column $ i $ are already occupied by bishwocks from column $ i-1 $**.\n\nThus, at column $ i $, we have:\n- The state $ s $: cells in column $ i $ already covered by previous bishwocks.\n- The pawn positions: which cells are blocked.\n\nWe can place a bishwock starting at column $ i $ only if the three cells it covers are:\n- Not blocked by pawns, and\n- Not already covered by a previous bishwock (i.e., not in state $ s $ for column $ i $, and not blocked in column $ i+1 $).\n\nWe consider placing **one** bishwock (or none) at column $ i $, and then move to column $ i+1 $.\n\nWe also consider the possibility of placing **two** bishwocks overlapping? No, each cell can be covered only once.\n\nActually, at one column, we can place at most one bishwock, since each bishwock uses two columns and three cells, and we only have two cells per column.\n\nSo at each column $ i $, we consider:\n\n- Option 1: Place no bishwock starting at $ i $. Then the state for column $ i+1 $ is 0 (no coverage from left), **but** we must account for the fact that the current column $ i $ may have some free cells left — that’s fine.\n\nWait, no: the state for the next column should reflect whether any cell in column $ i $ is covered by a bishwock that started at $ i-1 $ — which is already encoded in $ s $. When we move to column $ i+1 $, the only coverage from the left is from bishwocks placed at column $ i $.\n\nSo if we place a bishwock starting at $ i $, it will cover one or two cells in column $ i+1 $, and we update the state accordingly.\n\nIf we place no bishwock at $ i $, then column $ i+1 $ has no bishwock extending from the left → state = 0.\n\nBut we must ensure that we are not \"leaving\" a cell in column $ i $ uncovered that could have been used — but since we are maximizing, and bishwocks are L-shaped, we can always delay placement.\n\nThus, recurrence:\n\nFor each column $ i \\in [0, n-1] $, and state $ s \\in \\{0,1,2,3\\} $:\n\n- Let $ a_0 = \\text{free}[0][i] \\land \\neg (s \\& 1) $  // top cell available at column $ i $\n- Let $ a_1 = \\text{free}[1][i] \\land \\neg (s \\& 2) $  // bottom cell available at column $ i $\n\nIf $ i == n-1 $: we cannot place any bishwock starting here (needs column $ i+1 $), so only option is to move to end.\n\nOtherwise:\n\nOption 1: Place no bishwock at $ i $.  \nThen $ dp[i+1][0] = \\max(dp[i+1][0], dp[i][s]) $\n\nOption 2: Try each of the four bishwock types, if possible.\n\nFor each type, check:\n- The three required cells are available (i.e., not blocked by pawn and not already covered)\n- The two cells in column $ i+1 $ are not blocked by pawns\n\nThen compute the new state for column $ i+1 $, and update.\n\nThe four types:\n\n1. Type A: covers (0,i), (1,i), (0,i+1)  \n   → needs: a0, a1, and free[0][i+1]  \n   → covers column $ i+1 $ at top → new state = 1  \n   → update: $ dp[i+1][1] = \\max(dp[i+1][1], dp[i][s] + 1) $\n\n2. Type B: covers (0,i), (1,i), (1,i+1)  \n   → needs: a0, a1, free[1][i+1]  \n   → covers column $ i+1 $ at bottom → new state = 2  \n   → update: $ dp[i+1][2] = \\max(dp[i+1][2], dp[i][s] + 1) $\n\n3. Type C: covers (1,i), (0,i+1), (1,i+1)  \n   → needs: a1, free[0][i+1], free[1][i+1]  \n   → covers column $ i+1 $ at top → new state = 1  \n   → update: $ dp[i+1][1] = \\max(dp[i+1][1], dp[i][s] + 1) $\n\n4. Type D: covers (0,i), (0,i+1), (1,i+1)  \n   → needs: a0, free[0][i+1], free[1][i+1]  \n   → covers column $ i+1 $ at bottom → new state = 2  \n   → update: $ dp[i+1][2] = \\max(dp[i+1][2], dp[i][s] + 1) $\n\nInitial state: $ dp[0][0] = 0 $, and for $ s \\neq 0 $, $ dp[0][s] = -\\infty $ (impossible)\n\nFinal answer: $ \\max(dp[n][0], dp[n][1], dp[n][2], dp[n][3]) $\n\nBut note: at column $ n $, we have processed all columns. Since bishwocks cannot extend beyond column $ n-1 $, any state at column $ n $ is acceptable — we just take the max.\n\nThis DP runs in $ O(n \\times 4) = O(n) $, which is efficient for $ n \\leq 100 $.\n\n**Final Mathematical Formulation:**\n\nLet $ n $ be the length of the input strings.  \nLet $ b_0, b_1 \\in \\{0,1\\}^n $, where $ b_r[i] = 1 $ if the cell at row $ r $, column $ i $ is empty (`'0'`), else $ 0 $.\n\nDefine $ dp[i][s] $ for $ i \\in \\{0, 1, \\dots, n\\} $, $ s \\in \\{0,1,2,3\\} $, as the maximum number of bishwocks that can be placed in columns $ 0 $ to $ i-1 $, with $ s $ encoding the coverage of column $ i $ by bishwocks from column $ i-1 $:\n\n- $ s = 0 $: no cell in column $ i $ is covered by a bishwock from column $ i-1 $\n- $ s = 1 $: only cell $ (0,i) $ is covered\n- $ s = 2 $: only cell $ (1,i) $ is covered\n- $ s = 3 $: both cells are covered\n\nInitial condition:  \n$ dp[0][0] = 0 $, and $ dp[0][s] = -\\infty $ for $ s \\in \\{1,2,3\\} $\n\nFor each $ i \\in \\{0, 1, \\dots, n-1\\} $ and each $ s \\in \\{0,1,2,3\\} $, if $ dp[i][s] > -\\infty $:\n\nLet  \n- $ a_0 = b_0[i] \\land \\neg (s \\& 1) $  \n- $ a_1 = b_1[i] \\land \\neg (s \\& 2) $\n\n**Option 1**: Do not place any bishwock starting at column $ i $:  \n→ $ dp[i+1][0] \\gets \\max(dp[i+1][0], dp[i][s]) $\n\n**Option 2**: Place bishwock of type A if $ a_0 \\land a_1 \\land b_0[i+1] $:  \n→ $ dp[i+1][1] \\gets \\max(dp[i+1][1], dp[i][s] + 1) $\n\n**Option 3**: Place bishwock of type B if $ a_0 \\land a_1 \\land b_1[i+1] $:  \n→ $ dp[i+1][2] \\gets \\max(dp[i+1][2], dp[i][s] + 1) $\n\n**Option 4**: Place bishwock of type C if $ a_1 \\land b_0[i+1] \\land b_1[i+1] $:  \n→ $ dp[i+1][1] \\gets \\max(dp[i+1][1], dp[i][s] + 1) $\n\n**Option 5**: Place bishwock of type D if $ a_0 \\land b_0[i+1] \\land b_1[i+1] $:  \n→ $ dp[i+1][2] \\gets \\max(dp[i+1][2], dp[i][s] + 1) $\n\nFinal answer:  \n$ \\max_{s \\in \\{0,1,2,3\\}} dp[n][s] $\n\nThis is the formal mathematical representation.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF991D","tags":["dp","greedy"],"sample_group":[["00\n00","1"],["00X00X0XXX0\n0XXX0X00X00","4"],["0X0X0\n0X0X0","0"],["0XXX0\n00000","2"]],"created_at":"2026-03-03 11:00:39"}}