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>