Parity Game
题意翻译
你和北极熊 Alice 和北极熊 Bob 一起钓鱼。他们等鱼上钩等得很无聊,于是想到了一个游戏来消磨时间。首先,Alice 和 Bob 分别写下一个 01 串(只包含”0”和“1”的字符串)$a$ 和 $b$,然后你可以通过两种操作尝试将 $a$ 变成 $b$:
- 将 $parity(a)$ 添加到 $a$ 的末尾。例如:$1010 \rightarrow 10100$。
- 删除 $a$ 的第一个字符。例如:$1001 \rightarrow 001$。若 $a$ 为空串则无法进行此操作。
你可以进行任意多次操作。现在请你求出是否能将 $a$ 变为 $b$。
如果一个 01 串中有奇数个 $1$,那么这个 01 串的 $parity$ 值是 $1$,否则是 $0$。
## 输入输出格式
### 输入格式
第一行为 01 串 $a$,第二行为 01 串 $b$($1 \le |a|, |b| \le 1000$)。其中 $|x|$ 表示串 $x$ 的长度。
### 输出格式
如果可能将 $a$ 变为 $b$ 则输出 `YES`,否则输出 `NO`。
题目描述
You are fishing with polar bears Alice and Bob. While waiting for the fish to bite, the polar bears get bored. They come up with a game. First Alice and Bob each writes a 01-string (strings that only contain character "0" and "1") $ a $ and $ b $ . Then you try to turn $ a $ into $ b $ using two types of operations:
- Write $ parity(a) $ to the end of $ a $ . For example, ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF297A/ffa9ba2c96c1525e244bb8f0304768bf297c672a.png).
- Remove the first character of $ a $ . For example, ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF297A/2a7b23121f5c760f7810c0db14858af4bcbe6719.png). You cannot perform this operation if $ a $ is empty.
You can use as many operations as you want. The problem is, is it possible to turn $ a $ into $ b $ ?
The $ parity $ of a 01-string is $ 1 $ if there is an odd number of "1"s in the string, and $ 0 $ otherwise.
输入输出格式
输入格式
The first line contains the string $ a $ and the second line contains the string $ b $ $ (1<=|a|,|b|<=1000) $ . Both strings contain only the characters "0" and "1". Here $ |x| $ denotes the length of the string $ x $ .
输出格式
Print "YES" (without quotes) if it is possible to turn $ a $ into $ b $ , and "NO" (without quotes) otherwise.
输入输出样例
输入样例 #1
01011
0110
输出样例 #1
YES
输入样例 #2
0011
1110
输出样例 #2
NO
说明
In the first sample, the steps are as follows: $ 01011→1011→011→0110 $