Vizualizare sursă pentru „3944 - Turn 1”

== Enunț ==
Se consideră <code>n</code> cuburi numerotate de la <code>1</code> la <code>n</code> pentru care se cunosc latura și culoarea. Să se genereze toate turnurile de înălțime <code>H</code> ce se pot forma cu cele <code>n</code> 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 <code>turn_1IN.txt</code> conține pe prima linie două numere naturale <code>n</code> și <code>H</code>, iar pe următoarele <code>n</code> linii descrierea cuburilor. Linia <code>i+1</code> conține descrierea cubului <code>i</code> sub forma: ''latură culoare''.

= Date de ieșire =
Fișierul de ieșire <code>turn_1OUT.txt</code> 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 <code>H</code>.

= Restricții și precizări =

* <code>1 ≤ n < 15</code>
* <code>1 ≤ H ≤ 50</code>
* <code>1 ≤ latura ≤ 10</code>
* <code>culorile sunt șiruri de caractere cu cel mult 20 de litere și sunt scrise cu litere mici</code>
* nu există cuburi identice
* pentru datele de intrare există întotdeauna soluție

= Exemplu 1: =
<code>turn_1IN.txt</code>
 5 5
 1 alb
 2 alb
 1 roz
 2 roz
 3 alb
<code>turn_1OUT.txt</code>
 2 4 1 
 4 2 3 
 5 3 1 
 5 4 

=== Explicație ===
Primul turn este format din cuburile: <code>2 (2,alb), 4 (2,roz), 1 (1,alb)</code>.

Al doilea turn este format din cuburile: <code>4 (2,roz), 2 (2,alb), 3 (1,roz)</code>

etc.

== Exemplu 2: ==
<code>turn_1IN.txt</code>
 16 5
 1 alb
 2 alb
 1 roz
 2 roz
 3 alb
<code>turn_1OUT.txt</code>
 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>