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:

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