0204 - Siruri

Cerinţa

Se citesc două numere naturale nenule n și m. Să se determine toate şirurile cu m elemente din mulţimea {1,2,..,n}, ordonate strict crescător, cu proprietatea că oricare două elemente consecutive în şir au diferenţa mai mică sau egală cu cu 2.

Date de intrare

Fişierul de intrare siruriIN.txt conţine pe prima linie numerele n și m, separate printr-un spațiu.

Date de ieşire

Fişierul de ieşire siruriOUT.txt va conţine pe fiecare linie câte m valori, separate prin câte un spaţiu, reprezentând elementele unui şir. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

Restricţii şi precizări

• 1 ≤ m ≤ n ≤ 15
• şirurile vor fi afişate în ordine lexicografică

Exemplul 1

siruriIN.txt

5 3

siruriOUT.txt

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

Exemplul 2

siruriIN.txt

8 9

siruriOUT.txt

Nu corespunde restricțiilor

Rezolvare

def genereaza_siruri(n, m, sir_curent, start):
    if len(sir_curent) == m:
        return [sir_curent.copy()]

    siruri = []
    for i in range(start, n + 1):
        if not sir_curent or abs(sir_curent[-1] - i) <= 2:
            sir_curent.append(i)
            siruri.extend(genereaza_siruri(n, m, sir_curent, i + 1))
            sir_curent.pop()

    return siruri

def main():
    with open("siruriIN.txt", "r") as fisier_intrare:
        n, m = map(int, fisier_intrare.readline().split())

    if not (1 <= m <= n <= 15):
        with open("siruriOUT.txt", "w", encoding="utf-8") as fisier_iesire:
            fisier_iesire.write("Nu corespunde restricțiilor\n")
        return

    siruri_generate = genereaza_siruri(n, m, [], 1)

    with open("siruriOUT.txt", "w", encoding="utf-8") as fisier_iesire:
        if not siruri_generate:
            fisier_iesire.write("Nu corespunde restricțiilor\n")
        else:
            for sir in sorted(siruri_generate):
                fisier_iesire.write(" ".join(map(str, sir)) + "\n")

if __name__ == "__main__":
    main()