3921 - CainiSiPisici2
De la Universitas MediaWiki
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
#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)