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

<syntaxhighlight lang="python" line> 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()

</syntaxhighlight>