1291 - CifreGen4

Cerința

Se dau două numere n m. Să se genereze toate numerele cu exact n cifre mai mici decât m cu proprietatea că diferența în valoare absolută dintre oricare două cifre consecutive este cel puțin 2.

Date de intrare

Programul citește de la tastatură numerele n m.

Date de ieșire

Programul va afișa pe ecran numerele generate, câte unul pe linie, în ordine crescătoare.

Restricții și precizări

• 1 ≤ n ≤ 7
• 0 < m < 6

Exemplu 1

Intrare

3 4

Iesire

130
131
202
203
302
303
313

Rezolvare

def read_input():
    n, m = map(int, input().strip().split())
    return n, m

def write_output(numbers):
    for number in numbers:
        print(number)

def is_valid(number, n, m):
    # Verifică dacă numărul are exact n cifre și fiecare cifră este mai mică decât m
    if len(number) != n:
        return False
    for digit in number:
        if int(digit) >= m:
            return False
    # Verifică dacă diferența dintre orice două cifre consecutive este cel puțin 2
    for i in range(1, len(number)):
        if abs(int(number[i]) - int(number[i - 1])) < 2:
            return False
    return True

def generate_numbers(n, m, current_number, numbers):
    if len(current_number) == n:
        if is_valid(current_number, n, m):
            numbers.append(current_number)
        return
    for digit in range(0, m):
        if len(current_number) == 0 and digit == 0:
            continue
        if len(current_number) == 0 or abs(int(current_number[-1]) - digit) >= 2:
            generate_numbers(n, m, current_number + str(digit), numbers)

def main():
    n, m = read_input()
    
    # Validări
    if not (1 <= n <= 7):
        raise ValueError("n trebuie să fie între 1 și 7")
    if not (0 < m < 6):
        raise ValueError("m trebuie să fie între 1 și 5")

    numbers = []
    generate_numbers(n, m, "", numbers)
    numbers.sort()
    write_output(numbers)

if __name__ == '__main__':
    main()