3943 - Cerc5
De la Universitas MediaWiki
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()