B. PolandBall and Game

Codeforces

IDCF755B

Time1000ms

Memory256MB

Difficulty—

binary searchdata structuresgamesgreedysortingsstrings

English · Original

Chinese · Translation

Formal · Original

PolandBall is playing a game with EnemyBall. The rules are simple. Players have to say words in turns. You cannot say a word which was already said. PolandBall starts. The Ball which can't say a new word loses. You're given two lists of words familiar to PolandBall and EnemyBall. Can you determine who wins the game, if both play optimally? ## Input The first input line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 103) — number of words PolandBall and EnemyBall know, respectively. Then _n_ strings follow, one per line — words familiar to PolandBall. Then _m_ strings follow, one per line — words familiar to EnemyBall. Note that one Ball **cannot** know a word more than once (strings are unique), but some words **can** be known by both players. Each word is non-empty and consists of no more than 500 lowercase English alphabet letters. ## Output In a single line of print the answer — "_YES_" if PolandBall wins and "_NO_" otherwise. Both Balls play optimally. [samples] ## Note In the first example PolandBall knows much more words and wins effortlessly. In the second example if PolandBall says _kremowka_ first, then EnemyBall cannot use that word anymore. EnemyBall can only say _wiedenska_. PolandBall says _wadowicka_ and wins.

PolandBall 正在与 EnemyBall 玩一个游戏。规则很简单：玩家轮流说出单词，不能说出之前已经说过的单词。PolandBall 先手。无法说出新单词的玩家输。给你两个列表，分别表示 PolandBall 和 EnemyBall 已知的单词。你能确定在双方都采取最优策略的情况下，谁会赢吗？第一行输入包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 103]）——分别表示 PolandBall 和 EnemyBall 已知的单词数量。接下来 #cf_span[n] 行，每行一个字符串——PolandBall 已知的单词。再接下来 #cf_span[m] 行，每行一个字符串——EnemyBall 已知的单词。注意，每个 Ball 不会重复知道同一个单词（字符串唯一），但某些单词可能被两个玩家都知道。每个单词非空，且由不超过 #cf_span[500] 个小写英文字母组成。请在一行中输出答案：如果 PolandBall 获胜，输出 "_YES_"；否则输出 "_NO_"。双方均采取最优策略。在第一个示例中，PolandBall 知道的单词多得多，轻松获胜。在第二个示例中，如果 PolandBall 首先说 _kremowka_，那么 EnemyBall 就不能再使用这个词。EnemyBall 只能说 _wiedenska_。PolandBall 再说 _wadowicka_ 并获胜。 ## Input 第一行输入包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 103]）——分别表示 PolandBall 和 EnemyBall 已知的单词数量。接下来 #cf_span[n] 行，每行一个字符串——PolandBall 已知的单词。再接下来 #cf_span[m] 行，每行一个字符串——EnemyBall 已知的单词。注意，每个 Ball 不会重复知道同一个单词（字符串唯一），但某些单词可能被两个玩家都知道。每个单词非空，且由不超过 #cf_span[500] 个小写英文字母组成。 ## Output 请在一行中输出答案：如果 PolandBall 获胜，输出 "_YES_"；否则输出 "_NO_"。双方均采取最优策略。 [samples] ## Note 在第一个示例中，PolandBall 知道的单词多得多，轻松获胜。在第二个示例中，如果 PolandBall 首先说 _kremowka_，那么 EnemyBall 就不能再使用这个词。EnemyBall 只能说 _wiedenska_。PolandBall 再说 _wadowicka_ 并获胜。

**Definitions** Let $ P $ be the set of words known only to PolandBall. Let $ E $ be the set of words known only to EnemyBall. Let $ B = P \cap E $ be the set of words known to both players. Let $ p = |P| $, $ e = |E| $, $ b = |B| $. **Constraints** $ 1 \leq p + b \leq 10^3 $, $ 1 \leq e + b \leq 10^3 $, All words are distinct strings of lowercase English letters, length ≤ 500. **Objective** Determine the winner under optimal play, with PolandBall starting. Players alternate turns, cannot repeat any word ever said. The player unable to move loses. The total number of distinct words is $ p + e + b $. Optimal play: both players will use shared words $ B $ strategically to force the opponent into a losing position. **Winning Condition** PolandBall wins if and only if: $$ p + b > e $$ Output "YES" if PolandBall wins, "NO" otherwise.

Samples

Input #1

5 1
polandball
is
a
cool
character
nope

Output #1

YES

Input #2

2 2
kremowka
wadowicka
kremowka
wiedenska

Output #2

YES

Input #3

1 2
a
a
b

Output #3

NO

API Response (JSON)

{
  "problem": {
    "name": "B. PolandBall and Game",
    "description": {
      "content": "PolandBall is playing a game with EnemyBall. The rules are simple. Players have to say words in turns. You cannot say a word which was already said. PolandBall starts. The Ball which can't say a new w",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF755B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "PolandBall is playing a game with EnemyBall. The rules are simple. Players have to say words in turns. You cannot say a word which was already said. PolandBall starts. The Ball which can't say a new w...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "PolandBall 正在与 EnemyBall 玩一个游戏。规则很简单：玩家轮流说出单词，不能说出之前已经说过的单词。PolandBall 先手。无法说出新单词的玩家输。\n\n给你两个列表，分别表示 PolandBall 和 EnemyBall 已知的单词。你能确定在双方都采取最优策略的情况下，谁会赢吗？\n\n第一行输入包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P $ be the set of words known only to PolandBall.  \nLet $ E $ be the set of words known only to EnemyBall.  \nLet $ B = P \\cap E $ be the set of words known to both players.  \n\n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments