3945 - Fazan Max
Cerința[edit | edit source]
Se dau n cuvinte distincte formate din litere mici. Afișați șirul format dintr-un număr maxim de cuvinte distincte dintre cele date, care respectă regula jocului Fazan. La jocul Fazan o succesiune de două cuvine a și b se consideră corectă dacă ultimele două litere din cuvântul a sunt identice cu primele două din b. De exemplu, cuvintele fazan și anterior sunt corecte în această ordine.
Date de intrare[edit | edit source]
Programul citește de la tastatură numărul n și apoi n cuvinte, separate prin spații sau scrise pe rânduri separate.
Date de ieșire[edit | edit source]
Programul va afișa pe ecran cuvintele care formează șirul cerut, separate prin câte un spațiu. Dacă există mai multe șiruri formate dintr-un număr maxim de cuvinte, se va afișa cel mai mic lexicografic.
Restricții și precizări[edit | edit source]
1 ≤ n ≤ 30 cele n cuvinte sunt formate din litere mici, au lungimea cel puțin 2 și cel mult 20 și sunt distincte. ==Exemplu==: Intrare
7 dor ana nasture repede alina diana decis Ieșire
alina nasture repede decis Explicație
Există mai multe soluții de lungime maximă, dar cea afișată este minimă lexicografic. Celelalte soluții sunt:
ana nasture repede decis diana nasture repede decis
Rezolvare[edit | edit source]
<syntaxhighlight lang="python3" line="1"> def backtracking(current_path, remaining_words, result):
if not remaining_words: # Verificăm dacă șirul format este mai lung sau la fel de lung ca rezultatul curent if len(current_path) > len(result): return current_path elif len(current_path) == len(result): # Verificăm dacă șirul curent este lexicografic mai mic current_str = " ".join(current_path) result_str = " ".join(result) if current_str < result_str: return current_path else: return result else: return result last_word = current_path[-1] if current_path else None for word in remaining_words: if last_word is None or last_word[-2:] == word[:2]: new_path = current_path + [word] new_remaining = remaining_words.copy() new_remaining.remove(word) result = backtracking(new_path, new_remaining, result) return result
Citirea datelor de intrare
n = int(input()) words = input().split()
Sortăm cuvintele pentru a îmbunătăți eficiența algoritmului
words.sort()
Inițializăm rezultatul cu primul cuvânt
initial_word = words.pop(0) result = backtracking([initial_word], words, [])
Afișăm rezultatul
print(" ".join(result)) </syntaxhighlight>