Andrada378 at 11:09, 5 January 2024

2024-01-05T11:09:03Z

Andrada378: Pagină nouă: '''''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...

2023-12-26T17:55:33Z

Pagină nouă: '''''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...

New page

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

def este_valid(ultim_cuvant, cuvant):

# Verifica daca ultimele doua litere ale cuvantului 'ultim_cuvant'

# sunt identice cu primele doua litere ale cuvantului 'cuvant'.

return ultim_cuvant[-2:] == cuvant[:2]

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

# Realizeaza algoritmul de backtracking pentru formarea șirului de cuvinte

# de lungime 'alese' care respectă regula jocului Fazan.

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

<nowiki>#</nowiki> Citire date de intrare

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

cuvinte = input().split()

<nowiki>#</nowiki> Apelare funcție pentru afișare rezultate

afiseaza_alegeri(cuvinte, m)

3942 - Fazan - Revision history

Andrada378 at 11:09, 5 January 2024