3945 - Fazan Max: Diferență între versiuni
Mraa (discuție | contribuții) (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...) |
Mraa (discuție | contribuții) Fără descriere a modificării |
||
Linia 27: | Linia 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> |
Versiunea curentă din 11 ianuarie 2024 18:17
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
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))