Editing 3690 - 2genc

== Cerința ==
Se dau 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 au urmatoarea proprietate: orice element al unei soluții este mai mare sau egal cu elementul anterior sau este mai mic decât elementul anterior cu 1.
== Date de intrare ==
Fișierul de intrare 2genc.in conține pe prima linie numerele n și m separate prin spațiu.
== Date de ieșire ==
Fișierul de ieșire 2genc.out va conține câte o soluție pe linie. Numerele de pe aceeași linie se separă prin spații.
== Restricții și precizări ==
*1 ≤ n ≤ 6
*1 ≤ m ≤ 9
== Exemplu 1 ==
;Intrare
4 3
;Iesire
1 1 1 <br>
1 1 2 <br>
1 1 3 <br>
1 1 4 <br>
1 2 1 <br>
1 2 2 <br>
1 2 3 <br>
1 2 4 <br>
1 3 2 <br>
1 3 3 <br>
1 3 4 <br>
1 4 3 <br>
1 4 4 <br>
2 1 1 <br>
2 1 2 <br>
2 1 3 <br>
2 1 4 <br>
2 2 1 <br>
2 2 2 <br>
2 2 3 <br>
2 2 4 <br>
2 3 2 <br>
2 3 3 <br>
2 3 4 <br>
2 4 3 <br>
2 4 4 <br>
3 2 1 <br>
3 2 2 <br>
3 2 3 <br>
3 2 4 <br>
3 3 2 <br>
3 3 3 <br>
3 3 4 <br>
3 4 3 <br>
3 4 4 <br>
4 3 2 <br>
4 3 3 <br>
4 3 4 <br>
4 4 3 <br>
4 4 4 
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input():
    with open("2genc.in", "r") as file:
        n, m = map(int, file.readline().strip().split())
    return n, m


def write_output(results):
    with open("2genc.out", "w") as file:
        for result in results:
            file.write(" ".join(map(str, result)) + "\n")


def generate_sequences(n, m):
    results = []

    def backtrack(sequence):
        if len(sequence) == m:
            results.append(sequence[:])
            return
        last = sequence[-1] if sequence else 0
        for i in range(1, n + 1):
            if not sequence or i >= last or i == last - 1:
                sequence.append(i)
                backtrack(sequence)
                sequence.pop()

    backtrack([])
    return results


def main():
    n, m = read_input()

    # Validări
    if not (1 <= n <= 6):
        raise ValueError("n trebuie să fie între 1 și 6")
    if not (1 <= m <= 9):
        raise ValueError("m trebuie să fie între 1 și 9")

    results = generate_sequences(n, m)
    write_output(results)


if __name__ == "__main__":
    main()
</syntaxhighlight>