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

1. Verifică dacă un număr este pătrat perfect

def este_patrat_perfect(x):

   return int(math.isqrt(x)) ** 2 == x

1. 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

1. 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"

1. 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>