Editing 2261 - Turn

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

= Exemplul 1: =
<code>turnIN.txt</code>
 5 5
 1 1
 2 1
 1 2
 2 2
 3 1
<code>turnOUT.txt</code>
 2 4 1 
 4 2 3 
 5 3 1 
 5 4 

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

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

etc.

== Exemplul 1: ==
<code>turnIN.txt</code>
 16 5
 1 1
 2 1
 1 2
 2 2
 3 1
<code>turnOUT.txt</code>
 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>