Mraa at 18:17, 11 January 2024

2024-01-11T18:17:27Z

@@ Line 27: / Line 27: @@
 diana nasture repede decis
 ==Rezolvare==
 def backtracking(current_path, remaining_words, result):
-    last_word = current_path[-1] if current_path else None
+   if not remaining_words:
-    for word in remaining_words:
+n = int(input()) words = input().split()
-    return result
+Sortăm cuvintele pentru a îmbunătăți eficiența algoritmului
-# Citirea datelor de intrare
+words.sort()
-# Sortăm cuvintele pentru a îmbunătăți eficiența algoritmului
+Inițializăm rezultatul cu primul cuvânt
-words.sort()
-# Inițializăm rezultatul cu primul cuvânt
+Afișăm rezultatul
 print(" ".join(result))

Mraa: 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...

2023-12-25T13:40:45Z

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...

New page

==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))

3945 - Fazan Max - Revision history

Mraa at 18:17, 11 January 2024