3689 - 2gen

Cerința

Se n și m numere naturale. Afișați în ordine lexicografică toate șirurile de lungime m care conțin numere de la 1 la n și fiecare valoare apare de maxim două ori.

Date de intrare

Fișierul de intrare 2genIN.txt conține pe prima linie numerele n și m separate prin spațiu.

Date de ieșire

Fișierul de ieșire 2genOUT.txt va conține câte o soluție pe linie. Numerele de pe aceeași linie se separă prin spații. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

Restricții și precizări

• 1 ≤ n ≤ 6
• 1 ≤ m ≤ 6

Exemplul 1

2genIN.txt

4 3

2genOUT.txt

1 1 2 
1 1 3 
1 1 4 
1 2 1 
1 2 2 
1 2 3 
1 2 4 
1 3 1 
1 3 2 
1 3 3 
1 3 4 
1 4 1 
1 4 2 
1 4 3 
1 4 4 
2 1 1 
2 1 2 
2 1 3 
2 1 4 
2 2 1 
2 2 3 
2 2 4 
2 3 1 
2 3 2 
2 3 3 
2 3 4 
2 4 1 
2 4 2 
2 4 3 
2 4 4 
3 1 1 
3 1 2 
3 1 3 
3 1 4 
3 2 1 
3 2 2 
3 2 3 
3 2 4 
3 3 1 
3 3 2 
3 3 4 
3 4 1 
3 4 2 
3 4 3 
3 4 4 
4 1 1 
4 1 2 
4 1 3 
4 1 4 
4 2 1 
4 2 2 
4 2 3 
4 2 4 
4 3 1 
4 3 2 
4 3 3 
4 3 4 
4 4 1 
4 4 2 
4 4 3 

Exemplul 2

2genIN.txt

7 7 

consola

Nu corespunde restricțiilor

Rezolvare

def genereaza_siruri(n, m):
    def backtracking(sir_partial):
        if len(sir_partial) == m:
            solutii.append(sir_partial.copy())
            return

        for numar in range(1, n + 1):
            if folosit[numar] < 2:
                sir_partial.append(numar)
                folosit[numar] += 1

                backtracking(sir_partial)

                sir_partial.pop()
                folosit[numar] -= 1

    solutii = []
    folosit = {numar: 0 for numar in range(1, n + 1)}
    backtracking([])

    return solutii


def main():
    # Citire date de intrare
    with open("2genIN.txt", "r") as fisier_intrare:
        n, m = map(int, fisier_intrare.readline().split())

    # Verificare restricții
    if not (1 <= n <= 6 and 1 <= m <= 6):
        print("Nu corespunde restricțiilor")
        return

    # Generare șiruri
    siruri = genereaza_siruri(n, m)

    # Scriere rezultate în fișierul de ieșire
    with open("2genOUT.txt", "w") as fisier_iesire:
        if siruri:
            for sir in siruri:
                fisier_iesire.write(" ".join(map(str, sir)) + "\n")
        else:
            fisier_iesire.write("Nu corespunde restricțiilor\n")


if __name__ == "__main__":
    main()