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

<syntaxhighlight lang="python3" line="1"> 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)

</syntaxhighlight>