3945 - Fazan Max: Difference between revisions

From Bitnami MediaWiki
Mraa (talk | contribs)
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 (talk | contribs)
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
  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


    for word in remaining_words:
n = int(input()) words = input().split()
        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
Sortăm cuvintele pentru a îmbunătăți eficiența algoritmului


# Citirea datelor de intrare
words.sort()
n = int(input())
words = input().split()


# Sortăm cuvintele pentru a îmbunătăți eficiența algoritmului
Inițializăm rezultatul cu primul cuvânt
words.sort()
 
initial_word = words.pop(0) result = backtracking([initial_word], words, [])


# Inițializăm rezultatul cu primul cuvânt
Afișăm rezultatul
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>