2904 - Sum Triunghiular

Cerință

Se dă un număr natural n. Să se determine dacă numărul se poate scrie ca sumă de două numere triunghiulare. Dacă este posibil se vor afișa două numere triunghiulare a căror sumă este egală cu n, în orice ordine, respectiv mesajul NU în caz contrar.

Un număr triunghiular este numărul de puncte dintr-un triunghi echilateral umplut uniform cu puncte. De exemplu, 1, 3, 6, 10, 15 sunt numere triunghiulare.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran, în orice ordine, două numere triunghiulare care însumate dau numărul n, separate printr-un spațiu, sau mesajul NU dacă numărul nu poate fi scris ca suma de două numere triunghiulare.

Restricții și precizări

• n ≤ 10^12;
• numerele triunghiulare determinate pot fi identice.

Exemplul 1:

Intrare

24

Ieșire

3 21

Exemplul 2:

Intrare

15

Ieșire

NU

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

1. Definim o funcție pentru a calcula al n-lea număr triunghiular

def numar_triunghiular(n):

   return n * (n + 1) // 2

1. Definim o funcție pentru a verifica dacă un număr poate fi scris ca suma a două numere triunghiulare

def doua_numere_triunghiulare(n):

   i = 1
   # Parcurgem toate numerele triunghiulare până când ajungem la n
   while numar_triunghiular(i) < n:
       j = 1
       # Pentru fiecare număr triunghiular, verificăm dacă există un alt număr triunghiular astfel încât suma lor să fie egală cu n
       while numar_triunghiular(j) <= n - numar_triunghiular(i):
           if numar_triunghiular(i) + numar_triunghiular(j) == n:
               # Dacă găsim două astfel de numere, le returnăm
               return numar_triunghiular(i), numar_triunghiular(j)
           j += 1
       i += 1
   # Dacă nu găsim două astfel de numere, returnăm "NU"
   return "NU"

1. Acest bloc de cod este executat doar dacă acest script este rulat direct (nu este importat ca un modul)

if __name__ == "__main__":

   # Citim numărul de la tastatură
   n = int(input())
   # Apelăm funcția pentru a verifica dacă numărul poate fi scris ca suma a două numere triunghiulare
   rezultat = doua_numere_triunghiulare(n)
   # Afișăm rezultatul
   if rezultat == "NU":
       print(rezultat)
   else:
       print(*rezultat)

</syntaxhighlight>