A1386. [COCI-2020-2021-contest3]#5 Vlak
编程题
提高+/省选-
知识点
题目描述
Nina and Emilija are playing a game on a piece of paper. Initially, the paper is empty.
In one move a player appends a letter to the end of the word that is currently written on the paper. They alternate turns, and Nina plays first.
Players must choose the letters in such a way that the following condition is met: the word that is written after the player’s move must be a prefix of some word in that players favourite song. If the player can’t make a move, she loses.
If both players play optimally, determine who wins.
In one move a player appends a letter to the end of the word that is currently written on the paper. They alternate turns, and Nina plays first.
Players must choose the letters in such a way that the following condition is met: the word that is written after the player’s move must be a prefix of some word in that players favourite song. If the player can’t make a move, she loses.
If both players play optimally, determine who wins.
输入格式
The first line contains a positive integer n, the number of words in Nina’s favourite song.
Each of the following n lines contains a word from Nina’s favourite song.
The following line contains a positive integer m, the number of words in Emilija’s favourite song.
Each of the following m lines contains a word from Emilija’s favourite song.
Words in input contain only lowercase letters, and the sum of the lengths of all words is at most 200 00
0.
Each of the following n lines contains a word from Nina’s favourite song.
The following line contains a positive integer m, the number of words in Emilija’s favourite song.
Each of the following m lines contains a word from Emilija’s favourite song.
Words in input contain only lowercase letters, and the sum of the lengths of all words is at most 200 00
0.
输出格式
Output Nina or Emilija, the name of the winner.
输入输出样例
输入 #1
2 aaa bbb 3 aab aba bbb
输出 #1
Nina
输入 #2
2 acg beh 2 adi bfj
输出 #2
Emilija
说明/提示
In test cases worth 40 points the sum of the lengths of the words will be at most 2000.
Clarification of the first example:
If Nina first writes b, Emilija must write b, and then Nina can write b. The current word is bbb, and
Emilija can’t make a move, so Nina wins.
If Nina would first write a, Emilija could write b. The word would be ab, and Nina wouldn’t be able to
make a move, and she would lose.
Clarification of the first example:
If Nina first writes b, Emilija must write b, and then Nina can write b. The current word is bbb, and
Emilija can’t make a move, so Nina wins.
If Nina would first write a, Emilija could write b. The word would be ab, and Nina wouldn’t be able to
make a move, and she would lose.