Submission #1078621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078621		xinyubb2000	Vlak (COCI20_vlak)	Cpython 3	70 / 70	296 ms	42584 KiB

Main

# 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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10