3942 - Fazan

Cerința

Se dau n cuvinte distincte formate din litere mici și un număr m. Afișați în ordine lexicografică toate șirurile de câte m 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ă numerele n și m, iar apoi n cuvinte, separate prin spații sau scrise pe rânduri separate.

Date de ieșire

Programul va afișa pe ecran pe linii separate în ordine lexicografică toate șirurile de câte m cuvinte dintre cele date, care respectă regula jocului Fazan. Cuvintele de pe același rând se vor separa prin câte un spațiu.

Dacă nu se pot alege m cuvinte care să respecte condiția, atunci se va afișa IMPOSIBIL.

Restricții și precizări

• 1 ≤ m < 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

11 3

cosmin nasture repede cosmina alina interactiv ascutit anual incrementare ananas banana

Ieșire

alina nasture repede

anual alina nasture

banana nasture repede

cosmin incrementare repede

cosmina nasture repede

Rezolvare

<syntaxhighlight lang="python"> def este_valid(ultim_cuvant, cuvant):

   # Verifică dacă ultimele două litere ale cuvântului 'ultim_cuvant'
   # coincid cu primele două litere ale cuvântului 'cuvant'.
   return ultim_cuvant[-2:] == cuvant[:2]

def backtracking(alese, cuvinte, solutie_parciala, rezultate):

   # Algoritmul de backtracking pentru formarea șirului de cuvinte.

   if alese == 0:
       rezultate.append(solutie_parciala[:])
       return

   ultim_cuvant = solutie_parciala[-1] if solutie_parciala else ""

   for cuvant in cuvinte:
       if cuvant not in solutie_parciala and este_valid(ultim_cuvant, cuvant):
           solutie_parciala.append(cuvant)
           backtracking(alese - 1, cuvinte, solutie_parciala, rezultate)
           solutie_parciala.pop()

def afiseaza_alegeri(cuvinte, m):

   # Afișează șirurile de cuvinte de lungime 'm' care respectă regula jocului Fazan.

   rezultate = []

   for cuvant in cuvinte:
       backtracking(m - 1, cuvinte, [cuvant], rezultate)

   rezultate = sorted(rezultate)

   if not rezultate:
       print("IMPOSIBIL")
   else:
       for solutie in rezultate:
           print(" ".join(solutie))

1. Funcție pentru validarea datelor de intrare

def validate_input(n, m, cuvinte):

   if not (1 <= m < n <= 30):
       print("Constrângeri neîndeplinite pentru n și m.")
       return False
   for cuvant in cuvinte:
       if not (2 <= len(cuvant) <= 20):
           print("Lungimea cuvintelor trebuie să fie între 2 și 20 caractere.")
           return False
   return True

1. Citire date de intrare

n, m = map(int, input().split()) cuvinte = input().split()

1. Validare date de intrare

if validate_input(n, m, cuvinte):

   # Apelare funcție pentru afișare rezultate
   afiseaza_alegeri(cuvinte, m)

</syntaxhighlight>