oj.uz

Submission #1078621

# Submission time Handle Problem Language Result Execution time Memory
1078621 2024-08-28T00:40:39 Z xinyubb2000 Vlak (COCI20_vlak) Python 3
70 / 70
 296 ms 42584 KB 
# revised by ChatGPT

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

    def has_children(self):
        return bool(self.children)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

def can_win(current_nodes, current_char):
    # Fetch Nina's current node based on the character
    nina_node = current_nodes[0].children.get(current_char)
    # Emilija's current node
    emilija_node = current_nodes[1]

    # If Nina's node is not valid or has no children, Nina can't continue, so she loses
    if not nina_node or not nina_node.has_children():
        return False

    # Explore all possible moves from the current character
    for next_char, next_nina_node in nina_node.children.items():
        # If Emilija can't win from this position, Nina wins
        if not can_win([emilija_node, next_nina_node], next_char):
            return True

    # If all possible moves still allow Emilija to win, Nina loses
    return False

# Create Trie structures for Nina and Emilija
nina_trie = Trie()
emilija_trie = Trie()

# Insert Nina's favorite words into her Trie
for _ in range(int(input())):
    nina_trie.insert(input().strip())

# Insert Emilija's favorite words into her Trie
for _ in range(int(input())):
    emilija_trie.insert(input().strip())

# Start the game with Nina's root node linked to the letter 'N'
nina_start = TrieNode()
nina_start.children['N'] = nina_trie.root

# Determine the winner and print the result
print('Nina' if can_win([nina_start, emilija_trie.root], 'N') else 'Emilija')

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3420 KB Output is correct
2 Correct 14 ms 3572 KB Output is correct
3 Correct 13 ms 3432 KB Output is correct
4 Correct 13 ms 3472 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3420 KB Output is correct
2 Correct 16 ms 3512 KB Output is correct
3 Correct 13 ms 3420 KB Output is correct
4 Correct 13 ms 3420 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3420 KB Output is correct
2 Correct 13 ms 3392 KB Output is correct
3 Correct 12 ms 3420 KB Output is correct
4 Correct 13 ms 3420 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3420 KB Output is correct
2 Correct 13 ms 3468 KB Output is correct
3 Correct 13 ms 3420 KB Output is correct
4 Correct 14 ms 3480 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 38736 KB Output is correct
2 Correct 246 ms 36436 KB Output is correct
3 Correct 198 ms 34724 KB Output is correct
4 Correct 296 ms 37932 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 40788 KB Output is correct
2 Correct 238 ms 42584 KB Output is correct
3 Correct 184 ms 39252 KB Output is correct
4 Correct 191 ms 39848 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 38036 KB Output is correct
2 Correct 214 ms 37184 KB Output is correct
3 Correct 184 ms 37976 KB Output is correct
4 Correct 242 ms 40204 KB Output is correct