3944 - Turn 1
Enunț
Se consideră n
cuburi numerotate de la 1
la n
pentru care se cunosc latura și culoarea. Să se genereze toate turnurile de înălțime H
ce se pot forma cu cele n
cuburi, astfel încât fiecare turn să respecte următoarele condiții:
- orice cub se așează peste un altul ce are latura mai mare sau egală cu a lui;
- să nu existe două cuburi consecutive de aceeași culoare;
Date de intrare
Fișierul de intrare turn_1IN.txt
conține pe prima linie două numere naturale n
și H
, iar pe următoarele n
linii descrierea cuburilor. Linia i+1
conține descrierea cubului i
sub forma: latură culoare.
Date de ieșire
Fișierul de ieșire turn_1OUT.txt
va conține soluțiile generate în ordinea lexicografică a indicilor. O soluție este validă dacă conține descrierea indicilor cuburilor care alcătuiesc turnul de înălțime H
.
Restricții și precizări
1 ≤ n < 15
1 ≤ H ≤ 50
1 ≤ latura ≤ 10
culorile sunt șiruri de caractere cu cel mult 20 de litere și sunt scrise cu litere mici
- nu există cuburi identice
- pentru datele de intrare există întotdeauna soluție
Exemplu 1:
turn_1IN.txt
5 5 1 alb 2 alb 1 roz 2 roz 3 alb
turn_1OUT.txt
2 4 1 4 2 3 5 3 1 5 4
Explicație
Primul turn este format din cuburile: 2 (2,alb), 4 (2,roz), 1 (1,alb)
.
Al doilea turn este format din cuburile: 4 (2,roz), 2 (2,alb), 3 (1,roz)
etc.
Exemplu 2:
turn_1IN.txt
16 5 1 alb 2 alb 1 roz 2 roz 3 alb
turn_1OUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
def afisare(b):
non_zero_values = [value for value in b if value != 0]
fout.write(" ".join(map(str, non_zero_values)) + '\n')
def verif(k):
if k > 1:
if col[b[k]] == col[b[k-1]]:
return False
if lat[b[k]] > lat[b[k-1]]:
return False
return True
def verifica_restrictii(n, h, lat, col):
if not (1 <= n < 15 and 1 <= h <= 50):
fout.write("Datele nu corespund restrictiilor impuse\n")
return False
for i in range(1, n + 1):
if not (1 <= lat[i] <= 10 and 1 <= len(col[i]) <= 20 and col[i].islower()):
fout.write("Datele nu corespund restrictiilor impuse\n")
return False
return True
def bkt(k, sp):
for i in range(1, n+1):
if viz[i] == 0:
b[k] = i
viz[i] = 1
sp += lat[b[k]]
if sp <= h and verif(k):
if sp == h:
afisare(b[:k+1])
else:
bkt(k+1, sp)
sp -= lat[b[k]]
viz[i] = 0
if __name__ == "__main__":
with open("turn_1IN.txt", 'r') as fin, open("turn_1OUT.txt", 'w') as fout:
n, h = map(int, fin.readline().split())
lat = [0] * 105
b = [0] * 105
sp = 0
viz = [0] * 105
col = [""] * 105
for i in range(1, n+1):
line = fin.readline().split()
if len(line) < 2:
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()
lat_str, col[i] = line
lat[i] = int(lat_str)
if not verifica_restrictii(n, h, lat, col):
exit()
bkt(1, sp)