2021 - Sumă Gauss2

Sursa: [1]

Cerinţa

Ana a calculat suma numerelor naturale mai mici sau egale cu n, iar Andreea suma numerelor naturale mai mici sau egale cu m. Doamna de mate a calculat apoi diferenţa celor două sume şi a obţinut rezultatul S.

Pentru o valoare S dată, aflaţi toate perechile (n,m), cu n>m, scriindu-le în ordine descrescătoare după n astfel încât doamna de mate să obţină rezultatul S.

Date de intrare

Fișierul de intrare sumagauss2.in conține pe prima linie numărul S.

Date de ieșire

Dacă datele introduse sunt corecte și respectă formatul așteptat, programul va afișa în continuare, pe un rând nou, perechile (n,m), cu n > m, în ordine descrescătoare după n.

În cazul în care datele din fișierul de intrare nu respectă restricțiile impuse programul va afișa pe ecran mesajul "Datele introduse nu corespund cerințelor." și nu va continua cu restul execuției programului.

Restricţii şi precizări

• 1 ⩽ S ⩽ 2.000.000.000

Exemplul 1

Intrare

sumagauss2.in

10

Ieșire

Datele corespund cerintelor.

sumagauss2.out

10 9

4 0

Exemplul 2

Intrare

sumagauss2.in

10000000000

Ieșire

Datele introduse nu corespund cerințelor.

Rezolvare

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

1. 2021

def validate_input(s):

   if not 1 <= s <= 2000000000:
       print("Datele introduse nu corespund cerințelor.")
       exit()

def read_input_file(input_file):

   with open(input_file, 'r') as f:
       s = int(f.readline().strip())
       validate_input(s)
       print("Datele corespund cerințelor.")
       return s

def write_output_file(output_file, solutions):

   with open(output_file, 'w') as f:
       for p in solutions:
           f.write(f"{p[0]} {p[1]}\n")

def find_solutions(s):

   solutions = []
   for n in range(s, 0, -1):
       sn = n * (n + 1) // 2
       for m in range(n):
           sm = m * (m + 1) // 2
           d = sn - sm
           if d == s and n > m:
               solutions.append((n, m))
   solutions.sort(reverse=True)
   return solutions

if __name__ == '__main__':

   # Citim numărul S din fișierul de intrare
   input_file = 'sumagauss2.in'
   s = read_input_file(input_file)

   # Găsim toate perechile (n, m) cu diferența dată S
   solutions = find_solutions(s)

   # Scriem perechile în ordine descrescătoare după n în fișierul de ieșire
   output_file = 'sumagauss2.out'
   write_output_file(output_file, solutions)

</syntaxhighlight>

Explicatie rezolvare

Acest program are rolul de a găsi toate perechile de numere naturale (n, m) astfel încât diferența dintre suma primelor n numere naturale și suma primelor m numere naturale să fie egală cu un anumit număr S dat.

Funcția "read_input_file" primește ca parametru numele fișierului de intrare și returnează numărul S citit din fișierul respectiv.

Funcția "write_output_file" primește ca parametri numele fișierului de ieșire și o listă de perechi (n, m) și scrie aceste perechi în fișierul de ieșire, fiecare pe o linie separată. Funcția "find_solutions" primește ca parametru numărul S și returnează o listă cu toate perechile (n, m) care îndeplinesc condiția dată, sortate descrescător după n.

În funcția "find_solutions", se parcurg toate numerele naturale de la s până la 1 și se calculează suma primelor n numere naturale pentru fiecare n, apoi se parcurg toate numerele naturale de la 0 până la n-1 și se calculează suma primelor m numere naturale pentru fiecare m. Se calculează diferența dintre aceste sume și se verifică dacă este egală cu numărul S dat. Dacă este, perechea (n, m) este adăugată la lista de soluții. La final, lista de soluții este sortată descrescător după n și returnată.

În blocul "if name == 'main'", se citește numărul S din fișierul de intrare, se găsesc toate perechile (n, m) cu diferența dată S folosind funcția "find_solutions", iar apoi se scriu perechile în ordine descrescătoare după n în fișierul de ieșire folosind funcția "write_output_file". Numele fișierelor de intrare și de ieșire sunt specificate în variabilele "input_file" și, respectiv, "output_file".