2427 - Sir 10

Sursa: [1]

Cerinţa

Gigel se distrează construind şiruri crescătoare de numere din mulţimea {1,2,…,n}. La un moment dat observă că unele şiruri, de cel puţin k termeni (k ≥ 3), au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru n ≥ 22:

2, 3, 4

1, 5, 9, 13

7, 10, 13, 16, 19, 22

Dându-se numărul natural n ajutați-l pe Gigel să numere câte astfel de șiruri poate să construiască.

Date de intrare

Programul conține pe prima linie numărul n.

Date de ieșire

Programul va conține pe prima linie numărul cerut.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează câte astfel de șiruri poate să construiască poate să construiască Gigel.

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

3 ≤ n ≤ 20000

3 ≤ k ≤ n

Exemplul 1

Datele de intrare

N este:

3

Datele de ieșire

Datele sunt introduse corect.

1

Exemplul 2

Datele de intrare

N este:

4

Datele de ieșire

Datele sunt introduse corect.

3

Exemplul 3

Datele de intrare

N este:

5

Datele de ieșire

Datele sunt introduse corect.

7

Rezolvare

<syntaxhighlight lang="python" line>

1. 2427

def has_valid_input(n, k):

   if not (3 <= n <= 20000):
       print("Datele nu corespund restricțiilor impuse.")
       return False
   if not (3 <= k <= n):
       print("Datele nu corespund restricțiilor impuse.")
       return False
   return True

if __name__ == '__main__':

   n = int(input("N este:"))
   k = 3
   nr_siruri = 0

   if not has_valid_input(n, k):
       exit()

   def has_property(sir):
       d = sir[1] - sir[0]
       for i in range(2, len(sir)):
           if sir[i] - sir[i - 1] != d:
               return False
       return True

   def backtracking(sir, pozitie):
       global nr_siruri
       if len(sir) >= k:
           if has_property(sir):
               nr_siruri += 1
       for i in range(pozitie + 1, n + 1):
           sir.append(i)
           backtracking(sir, i)
           sir.pop()

   backtracking([], 0)
   print("Datele sunt introduse corect.")
   print(nr_siruri)

</syntaxhighlight>

Explicatie cod:

Această parte de cod definește o funcție numită has_valid_input care primește două argumente, n și k. Această funcție este folosită pentru a valida intrarea utilizatorului și pentru a se asigura că valorile n și k respectă restricțiile de la 3 la 20000. Dacă nu sunt respectate, funcția va afișa un mesaj de eroare și va returna valoarea False. Dacă valorile sunt valabile, funcția va returna valoarea True.

În blocul principal de cod, programul întâi citește de la tastatură valoarea n. Apoi, variabila k este inițializată cu 3 și variabila nr_siruri este inițializată cu 0.

Apoi, se verifică dacă valorile de intrare sunt valide, apelând funcția has_valid_input. Dacă funcția returnează False, programul se oprește prin apelul exit().

Următoarele două funcții, has_property și backtracking, sunt definite în blocul principal de cod. Funcția has_property primește un șir de numere și verifică dacă acesta are proprietatea de a avea diferențe constante între elementele consecutive. Funcția backtracking generează toate combinațiile posibile de șiruri și le verifică folosind funcția has_property. Dacă un șir verifică condiția, numărul de șiruri găsite este incrementat.

În cele din urmă, programul afișează numărul de șiruri găsite.