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
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()