Editing 3943 - Cerc5

== Cerința ==
Se dă numărul natural n. Determinati o modalitate de așezare a numerelor din mulțimea 1,2,…,n
 pe un cerc astfel încât suma a oricare două nume învecinate să nu fie pătrat perfect.
== Date de intrare ==
Programul citește de la tastatură numărul n.
== Date de ieșire ==
Programul va afișa pe ecran cele n numere cerute, separate prin câte un spațiu.
== Restricții și precizări ==
*1 ≤ n ≤ 35
*dacă există mai multe modalități de aranjare a numerelor astfel încât să fie îndeplinită condiția, se poate afișa oricare;
*dacă nu există nicio modalitate de aranjare se va afișa mesajul nu exista

== Exemplu 1 ==
;Intrare
32

;Iesire
1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15



== Rezolvare ==
<syntaxhighlight lang="python" line>
import math


# Verifică dacă un număr este pătrat perfect
def este_patrat_perfect(x):
    return int(math.isqrt(x)) ** 2 == x


# Funcție de backtracking pentru a găsi o soluție validă
def backtrack(cerc, vizitat, n):
    if len(cerc) == n:
        # Verifică dacă primul și ultimul element formează un pătrat perfect
        return este_patrat_perfect(cerc[-1] + cerc[0])

    for i in range(1, n + 1):
        if not vizitat[i]:
            if not cerc or este_patrat_perfect(cerc[-1] + i):
                cerc.append(i)
                vizitat[i] = True
                if backtrack(cerc, vizitat, n):
                    return True
                cerc.pop()
                vizitat[i] = False
    return False


# Funcție pentru a găsi aranjarea corectă
def gaseste_aranjare(n):
    cerc = []
    vizitat = [False] * (n + 1)
    if backtrack(cerc, vizitat, n):
        return cerc
    else:
        return "nu exista"


# Funcția principală
def main():
    n = int(input().strip())
    rezultat = gaseste_aranjare(n)
    if isinstance(rezultat, list):
        print(" ".join(map(str, rezultat)))
    else:
        print(rezultat)


if __name__ == "__main__":
    main()


if __name__ == "__main__":
    main()

</syntaxhighlight>