2347 - Furnici

Sursa: [1]

Cerinţa

Lumea este în pericol. Încălzirea globală are efecte profunde în cele mai diferite domenii. Ea determină apariția extremelor climatice, topirea ghețarilor, ridicarea nivelului mărilor și, cel mai grav, dispariția a numeroase specii de animale. Cercetătorii au observat că cele mai afectate sunt furnicile.

Pentru a stabili cât de rapid este procesul de dispariție, ei și-au propus să le studieze timp de n zile, notând în fiecare zi numărul de furnici lucrătoare care ies după hrană. Ei au constatat că ele sunt afectate dacă, în zile consecutive, numărul de divizori ai numărului de furnici lucrătoare descrește. Vor lua în considerare doar perioadele de cel puțin două zile consecutive de descreșteri.

Pentru finalizarea studiului, trebuie să știe câte astfel de perioade au existat. Pentru că la calculele matematice pot greși, vă roagă să-i ajutați.

Dându-se un număr natural n, reprezentând numărul de zile în care se face studiul și apoi un șir x de n numere naturale, ce reprezintă șirul numerelor de furnici lucrătoare care ies după hrană, unde x reprezintă numărul de furnici lucrătoare din ziua i. Se cere să se determine numărul de secvențe maximale, ordonate strict descrescător după numărul de divizori, de lungime minim 2.

Date de intrare

Programul conţine două linii. Pe prima linie este scris numărul natural n, cu semnificația din cerință iar pe linia a doua, elementele șirului x, cu semnificația din cerință.

Date de ieșire

Programul va conţine un număr natural reprezentând numărul de secvențe maximale, de lungime minim 2, ordonate strict descrescător după numărul de divizori.

Dacă datele sunt introduse corect, programul va rula.

În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

2 ≤ n ≤ 100000

10 ≤ xi ≤ 1.000.000.000

Exemplul 1

Intrare

10

719 169 4065 813 289 101 123 516 516 1017

Ieșire

2

Rezolvare

<syntaxhighlight lang="python" line>

1. 2347

def numar_perioade(n, x):

   count = 0  # contor pentru perioade
   in_perioada = False  # variabilă pentru a ține evidența că suntem într-o perioadă
   for i in range(1, n):
       div_count = len([d for d in range(1, x[i-1]+1) if x[i-1] % d == 0])  # numărul de divizori al numărului anterior
       if div_count < len([d for d in range(1, x[i]+1) if x[i] % d == 0]):  # dacă numărul curent are mai mulți divizori decât cel anterior
           if in_perioada:  # dacă suntem deja într-o perioadă, nu o mai numărăm din nou
               continue
           count += 1
           in_perioada = True
       else:
           in_perioada = False  # ieșim din perioadă
   return count

if __name__ == '__main__':

   n = int(input("Introduceți numărul de zile: "))
   if not (2 <= n <= 100000):
       print("Eroare: n trebuie să fie între 2 și 100000")
       exit()
   x = [int(nr) for nr in input("Introduceți șirul de furnici lucrătoare: ").split()]
   if not all(10 <= xi <= 1000000000 for xi in x):
       print("Eroare: valorile din șir trebuie să fie între 10 și 1.000.000.000")
       exit()

   num_perioade = numar_perioade(n, x)
   print(f"Numărul de perioade de descreștere a numărului de divizori: {num_perioade}")

</syntaxhighlight>

Explicatie cod:

Această funcție, "numar_perioade(n, x)", primește două argumente: "n" - numărul de zile și "x" - o listă de numere întregi reprezentând numărul de divizori ai unui anumit număr de furnici în fiecare zi. Funcția returnează numărul de perioade în care numărul de divizori ai unei furnici scade.

În interiorul funcției, se definește un contor pentru perioade "count", o variabilă "in_perioada" care ține evidența dacă suntem într-o perioadă și se folosește o buclă "for" pentru a parcurge lista "x".

Pentru fiecare număr "x[i]", se calculează numărul de divizori ai numărului anterior "x[i-1]" și se salvează în variabila "div_count". Apoi se compară "div_count" cu numărul de divizori ai numărului curent "x[i]". Dacă numărul de divizori ai numărului curent este mai mare decât al celui anterior, atunci suntem într-o perioadă de scădere a numărului de divizori. Dacă suntem deja într-o perioadă, aceasta nu va fi numărată din nou, altfel se adaugă o nouă perioadă la contorul "count" și se setează variabila "in_perioada" la "True".

Dacă numărul de divizori ai numărului curent nu este mai mare decât al celui anterior, înseamnă că am ieșit dintr-o perioadă și variabila "in_perioada" este setată la "False".

În final, funcția returnează numărul de perioade de scădere a numărului de divizori.

Partea "if name == 'main':" verifică dacă script-ul este rulat ca program principal, adică nu este doar importat în alt script. Dacă acesta este cazul, programul începe să ruleze.

Înainte de a apela funcția "numar_perioade", programul verifică dacă numărul de zile "n" este între 2 și 100000 și dacă toate valorile din lista "x" sunt între 10 și 1000000000. Dacă aceste condiții nu sunt îndeplinite, programul afișează un mesaj de eroare și se încheie.

Dacă valorile introduse sunt corecte, funcția "numar_perioade" este apelată cu argumentele "n" și "x", iar rezultatul este afișat într-un mesaj de output.