1 files changed, 35 insertions, 0 deletions
diff --git a/problems/chainwords.py b/problems/chainwords.py
new file mode 100644
index 0000000..7e3794f
--- /dev/null
+++ b/problems/chainwords.py
@@ -0,0 +1,35 @@
+def can_win(words, current_word, used_words, memo):
+    state = (current_word, tuple(used_words))
+    if state in memo:
+        return memo[state]
+    
+    last_char = current_word[-1] if current_word else None
+    
+    for i, word in enumerate(words):
+        if not used_words[i] and (last_char is None or word[0] == last_char):
+            used_words[i] = True
+            if not can_win(words, word, used_words, memo):
+                used_words[i] = False
+                memo[state] = True
+                return True
+            used_words[i] = False
+    
+    memo[state] = False
+    return False
+
+def determine_winner(words):
+    n = len(words)
+    used_words = [False] * n
+    memo = {}
+    
+    if can_win(words, None, used_words, memo):
+        return "Alice"
+    else:
+        return "Bob"
+
+# Read input
+n = int(input())
+words = [input().strip() for _ in range(n)]
+
+# Determine the winner
+print(determine_winner(words))