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

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()