Editing 3945 - Fazan Max

==Cerința==
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==
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==
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==
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==
<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>