3921 - CainiSiPisici2

Cerința

Într-o curte se află câini și pisici. Să se genereze în ordine lexicografică șirurile formate din n animale, care :

încep cu câine și se termină cu pisică;

conțin cel mult m pisici;

nu conțin nicio pisică între doi câini.

Date de intrare

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

Date de ieșire

Programul va afișa pe rânduri separate ale ecranului șiruri formate din n caractere: 'C' (câine) sau 'P' (pisică), conform enunțului.

Restricții și precizări

• 1 ⩽ m ⩽ n *les; 20

Exemplul 1

Intrare

6 3

Ieșire

CCCCCP

CCCCPP

CCCPPP

CCPPCP

CPPCCP

Exemplul 2

Intrare

0 0

Ieșire

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 3921 - CainiSiPisici2

A = ['C', 'P']

def afisare(L):

   for i in range(1, L + 1):
       print(A[x[i]], end=)
   print()

def ok(k):

   if k == 1 and x[k] != 0:
       return False
   if k == n and x[k] != 1:
       return False
   if m < 0:
       return False
   if k > 2 and x[k] == 0 and x[k - 1] == 1 and x[k - 2] == 0:
       return False
   return True

def check_constraints(n, m):

   if not (1 <= m <= n <= 20):
       print("Nu au fost respectate cerintele impuse")
       return False
   return True

def back(k):

   global m
   for i in range(2):
       x[k] = i
       if i == 1:
           m -= 1
       if ok(k):
           if k == n:
               afisare(n)
           else:
               back(k + 1)
       if i == 1:
           m += 1

if __name__ == "__main__":

   n, m = map(int, input().split())

   if not check_constraints(n, m):
       exit()

   x = [0] * 21
   back(1)

</syntaxhighlight>