285
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ât10000
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; }
Comentarii