2261 - Turn

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 turnIN.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 turnOUT.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
• 1 ≤ culoare ≤ 5
• nu există cuburi identice
• pentru datele de intrare există întotdeauna soluție

Exemplul 1:

turnIN.txt

5 5
1 1
2 1
1 2
2 2
3 1

turnOUT.txt

2 4 1 
4 2 3 
5 3 1 
5 4 

Explicație

Primul turn este format din cuburile: 2 (2,1), 4 (2,2), 1 (1,1).

Al doilea turn este format din cuburile: 4 (2,2), 2 (2,1), 3 (1,2)

etc.

Exemplul 1:

turnIN.txt

16 5
1 1
2 1
1 2
2 2
3 1

turnOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def afis(k, st, out):

   out.write(" ".join(map(str, st[1:k + 1])) + '\n')

def vef(k, st, v):

   if v[st[k]]['y'] == v[st[k - 1]]['y']:
       return False
   if v[st[k]]['x'] > v[st[k - 1]]['x']:
       return False
   return True

def back(k, suma, st, uz, v, h, out):

   for i in range(1, len(v) + 1):
       if not uz[i]:
           uz[i] = 1
           st[k] = i
           suma += v[st[k]]['x']
           if k == 1 or (vef(k, st, v) and suma <= h):
               if suma == h:
                   afis(k, st, out)
               else:
                   back(k + 1, suma, st, uz, v, h, out)
           uz[i] = 0
           suma -= v[st[k]]['x']

def check_constraints(n, h, v):

   if not (1 <= n < 15 and 1 <= h <= 50):
       return False
   
   for i in range(1, n + 1):
       if not (1 <= v[i]['x'] <= 10 and 1 <= v[i]['y'] <= 5):
           return False
   
   return True

def main():

   with open("turnIN.txt", "r") as f_in, open("turnOUT.txt", "w") as f_out:
       n, h = map(int, f_in.readline().split())
       v = {}
       for i in range(1, n + 1):
           line = f_in.readline().split()
           if len(line) < 2:
               f_out.write("Datele nu corespund restrictiilor impuse\n")
               return
           x, y = map(int, line)
           v[i] = {'x': x, 'y': y}
       
       if not check_constraints(n, h, v):
           f_out.write("Datele nu corespund restrictiilor impuse\n")
       else:
           st = [0] * 1010
           uz = [0] * 101
           back(1, 0, st, uz, v, h, f_out)

if __name__ == "__main__":

   main()

</syntaxhighlight>