2710 - Cuv

Enunț

Se dau n cuvinte formate doar din litere mici. Trebuie construit un nou cuvânt C de n litere format astfel: prima literă a lui C este din primul cuvânt, a doua literă este din al doilea cuvânt, …, a n-a literă este din cel de-al n-lea cuvânt. În plus, literele cuvântului C trebuie să fie distincte.

Cerința

Să se determine cuvântul C minim lexicografic ce se poate forma utilizând litere distincte extrase din cuvintele inițiale.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n cuvinte separate prin spațiu.

Date de ieșire

Programul va afișa pe ecran cuvântul C minim lexicografic care se poate obține din litere distincte.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

Restricții și precizări

• 1 ≤ n ≤ 9
• Cele n cuvinte au cel puțin o literă și cel mult 6 litere
• Este garantat că C se poate forma din cuvintele inițiale

Exemplul 1:

Intrare

3
gem de caise

Ieșire

eda

Exemplul 2:

Intrare

10

Ieșire

"Datele nu corespund restrictiilor impuse"

Rezolvare:

<syntaxhighlight lang="python3" line="1"> def backtracking_permutations(words, current_permutation, used_letters, result):

   if len(current_permutation) == len(words):
       result.append(current_permutation)
       return

   current_word = words[len(current_permutation)]
   for letter in current_word:
       if letter not in used_letters:
           backtracking_permutations(
               words,
               current_permutation + letter,
               used_letters + letter,
               result
           )

def find_min_lexicographic_permutation(words):

   result = []
   backtracking_permutations(words, "", "", result)
   return min(result)

def check_restrictions(n, words):

   if n < 1 or n > 9:
       return False

   for word in words:
       if len(word) < 1 or len(word) > 6:
           return False

   return True

def main():

   try:
       n = int(input("Introduceti numarul de cuvinte: "))
       
       if n > 9:
           print("Datele nu corespund restrictiilor impuse.")
           return

       words = input("Introduceti cele %d cuvinte separate prin spațiu: " % n).split()

       if not check_restrictions(n, words):
           print("Datele nu corespund restrictiilor impuse.")
           return

       result = find_min_lexicographic_permutation(words)

       print("Cuvântul C minim lexicografic este:", result)
   except ValueError:
       print("Datele nu corespund restrictiilor impuse.")

if __name__ == "__main__":

   main()

</syntaxhighlight>