1327 - SirPIE

Cerinţa

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

Date de intrare

Fişierul de intrare sirpieIN.txtconţine pe prima linie numărul n, iar pe a doua linie n numere naturale.

Date de ieşire

Fişierul de ieşire sirpieOUT.txt 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

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

Exemplul 1:

sirpieIN.txt

4
8 6 7 9

sirpieOUT.txt

6 7 8 9 
6 7 9 8 
8 9 7 6 
9 8 7 6 

Exemplul 2:

sirpieIN.txt

11
8 6 7 9

sirpieOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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)