Editing 1327 - SirPIE

= Cerinţa =
Se citeşte un număr natural nenul <code>n</code>, apoi <code>n</code> numere naturale distincte. Să se afişeze, în ordine lexicografică, șirurile din cele <code>n</code> valori cu proprietatea că oricare două valori învecinate sunt prime între ele.

= Date de intrare =
Fişierul de intrare <code>sirpieIN.txt</code>conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale.

= Date de ieşire =
Fişierul de ieşire <code>sirpieOUT.txt</code> va conţine pe fiecare linie elementele unei șir, separate prin câte un spaţiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n < 10</code>
* cele <code>n</code> numere de pe a doua linie a fişierului de intrare sunt mai mici decât <code>10000</code>

= Exemplul 1: =
<code>sirpieIN.txt</code>
 4
 8 6 7 9
<code>sirpieOUT.txt</code>
 6 7 8 9 
 6 7 9 8 
 8 9 7 6 
 9 8 7 6 

= Exemplul 2: =
<code>sirpieIN.txt</code>
 11
 8 6 7 9
<code>sirpieOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_constraints(n, v, fout):
    if not (1 <= n < 10):
        fout.write("Datele nu corespund restrictiilor impuse\n")
        return False

    for num in v:
        if not (1 <= num < 10000):
            fout.write("Datele nu corespund restrictiilor impuse\n")
            return False

    return True

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def afisare_sol(sol, fout):
    fout.write(" ".join(map(str, sol)) + "\n")

def back(k, prev, fout):
    if k == n:
        afisare_sol(sol, fout)
    else:
        for i in range(n):
            if not folosit[i] and gcd(v[i], prev) == 1:
                sol[k] = v[i]
                folosit[i] = True
                back(k + 1, v[i], fout)
                folosit[i] = False

if __name__ == "__main__":
    with open("sirpieIN.txt", "r") as fin, open("sirpieOUT.txt", "w") as fout:
        n = int(fin.readline().strip())
        v = list(map(int, fin.readline().split()))

        if not check_constraints(n, v, fout):
            # Exit if constraints are not met
            exit()

        sol = [0] * n
        folosit = [False] * n

        # Sorting
        v.sort()

        back(0, 1, fout)

</syntaxhighlight>