3945 - Fazan Max: Difference between revisions
Pagină nouă: ==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... |
No edit summary |
||
Line 27: | Line 27: | ||
diana nasture repede decis | diana nasture repede decis | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3" line="1"> | |||
def backtracking(current_path, remaining_words, result): | 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() | |||
words | |||
Inițializăm rezultatul cu primul cuvânt | |||
words. | |||
initial_word = words.pop(0) result = backtracking([initial_word], words, []) | |||
Afișăm rezultatul | |||
print(" ".join(result)) | print(" ".join(result)) | ||
</syntaxhighlight> |
Latest revision as of 18:17, 11 January 2024
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>