991D.md (1675B)
1 Source: https://codeforces.com/problemset/problem/991/D 2 3 D. Bishwock 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 ``` 24 XX XX .X X. 25 X. .X XX XX 26 ``` 27 28 Bishwocks don't attack any squares and can even occupy on the adjacent squares as long as they don't occupy the same square. 29 30 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. 31 32 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. 33 34 Input 35 36 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$. 37 38 Output 39 40 Output a single integer — the maximum amount of bishwocks that can be placed onto the given board. 41 42 Examples 43 44 Input 45 46 ``` 47 00 48 00 49 ``` 50 51 Output 52 53 ``` 54 1 55 ``` 56 57 Input 58 59 ``` 60 00X00X0XXX0 61 0XXX0X00X00 62 ``` 63 64 Output 65 66 ``` 67 4 68 ``` 69 70 Input 71 72 ``` 73 0X0X0 74 0X0X0 75 ``` 76 77 Output 78 79 ``` 80 0 81 ``` 82 83 Input 84 85 ``` 86 0XXX0 87 00000 88 ``` 89 90 Output 91 92 ``` 93 2 94 ```