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 sirpie.in conţine pe prima linie numărul n, iar pe a doua linie n numere naturale.

Date de ieşire

Fişierul de ieşire sirpie.out va conţine pe fiecare linie elementele unei șir, separate prin câte un spaţiu.

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

Exemplu

sirpie.in

4
8 6 7 9

sirpie.out

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

#include <bits/stdc++.h>

using namespace std;

ifstream cin("sirpie.in");
ofstream cout("sirpie.out");

int n , x[10] , p[10] , a[10];

int cmmdc(int a , int b)
{
    int r;
    while(b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    if(a == 1)return 1;
    else return 0;
}

void afisare()
{
    int ok = 0;
    for(int i = 1 ; i < n ; ++i)
        if(!cmmdc(a[x[i]] , a[x[i+1]])) ok = 1;
    if(ok == 0)
    {
        for(int i = 1 ; i <= n ; ++i)
            cout << a[x[i]] << ' ';
        cout << endl;
    }
}

void back(int k)
{
    for(int i = 1 ; i <= n ; i++)
        if(!p[i])
        {
            x[k] = i;
            p[i] = 1;
            if(k == n) afisare();
            else back(k + 1);
            p[i] = 0;
        }
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    sort(a + 1 , a + n + 1);
    back(1);
    return 0;
}