#include <bits/stdc++.h>
using namespace std;
struct node {
map<char, int> nxt;
int &operator[](char c) {
return nxt[c];
}
};
struct trie {
vector<node> t;
int new_node() {
t.push_back(node());
return (int) t.size() - 1;
}
trie() {
t.clear();
new_node();
}
void insert(string &s) {
int u = 0;
for (char &c: s) {
if (!t[u][c]) {
t[u][c] = new_node();
}
u = t[u][c];
}
}
} tn, te;
vector<vector<vector<int> > > dp;
bool rc(int turn, int nina, int emilija) {
auto &ret = dp[turn][nina][emilija];
if (~ret) return ret;
bool win = false;
int new_nina = nina, new_emilija = emilija;
for (char c = 'a'; c <= 'z'; c++) {
if (turn) {
new_emilija = te.t[emilija][c];
if (!new_emilija) continue;
if (!tn.t[nina][c]) {
win = true;
break;
}
auto ops = rc(0, tn.t[nina][c], new_emilija);
if (!ops) {
win = true;
break;
}
} else {
new_nina = tn.t[nina][c];
if (!new_nina) continue;
if (!te.t[emilija][c]) {
win = true;
break;
}
auto ops = rc(1, new_nina, te.t[emilija][c]);
if (!ops) {
win = true;
break;
}
}
}
return ret = win;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
tn.insert(s);
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string s;
cin >> s;
te.insert(s);
}
dp.assign(2, vector<vector<int> >(tn.t.size(), vector<int>(te.t.size(), -1)));
cout << (rc(0, 0, 0) ? "Nina" : "Emilija");
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |