3732 - Seism

Cercetătorii de la NASA au instalat pe Marte un seismograf cu ajutorul căruia s-au înregistrat mișcările la nivelul solului planetei. Seismograful a trimis în fiecare din cele N secunde ce definesc perioada de timp analizată, câte un semnal pe Pământ ce a fost codificat de cercetători cu valoarea 1, dacă seismograful a detectat mișcare și 0, în cazul în care nu s-a înregistrat mișcare la nivelul solului planetei. Astfel, un seism de pe Marte a fost definit de cercetători ca fiind o perioadă continuă de timp în care seismograful a trimis, din secundă în secundă, câte un semnal codificat cu 1 și care începe după cel puțin două semnale codificate cu 0, iar la sfârșitul ei sunt înregistrate cel puțin două semnale codificate cu 0.

Cerința

Cunoscând șirul celor N valori transmise în ordine de seismograf, scrieți un program care să determine:

1. Care a fost durata maximă, exprimată în secunde a unui seism;

2. Câte seisme au avut loc în perioada de timp analizată;

3. Din cauza unei erori tehnice, o perioadă continuă de timp seismograful a transmis eronat. Astfel, în șirul inițial format din cele N semnale, trebuie să înlocuim valoarea 0 cu valoarea 1, într-o singură secvență, de lungime nevidă, de elemente nule alăturate. Analizând toate posibilitățile de a face această modificare, determinați durata maximă a unui seism care se obține după modificarea șirului inițial de semnale.

Date de intrare

Fișierul de intrare seism.in conține pe prima linie un număr natural C care poate avea valorile 1, 2 sau

3 și reprezintă numărul cerinței. Pe cea de-a doua linie, un număr natural N având semnificația din enunț. Pe următoarea linie, N numere naturale despărțite prin câte un spațiu, reprezentând codificarea semnalului transmis de seismograf, din secundă în secundă, începând cu secunda 1 și până la secunda N.

Date de ieșire

Fișierul de ieșire seism.out va conține pe prima linie un singur număr natural reprezentând rezultatul

determinat conform cerinței.

Restricții și precizări

• 5 ≤ N ≤ 100.000
• Un seism durează între 1 și N - 4 secunde
• Pentru cerințele 1 și 2 se garantează că seismograful a detectat cel puțin un seism.
• La cerința 3 se garantează că există cel puțin o secvență nevidă de elemente egale cu 0 ce pot fi schimbate în 1 pentru a avea cel puțin un seism în tot șirul.
• Pentru rezolvarea corectă a primei cerințe se obțin 40 de puncte, pentru rezolvarea corectă a celei de a doua cerințe se obțin 40 de puncte, iar pentru rezolvarea corectă a celei de a treia cerințe se obțin 20 de puncte.

Exemplu :

seism.in

1
21
0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0
0 1

seism.out

4

Explicație

Durata maximă a unui seism este de 4 secunde.

<syntaxhighlight lang="python" line="1"> def analyze_seismic_data(signals):

   n = len(signals)
   
   # Durata maximă a unui seism și numărul total de seisme
   max_seism_duration = 0
   total_seisms = 0
   current_duration = 0
   in_seism = False
   
   for i in range(n):
       if signals[i] == 1:
           if not in_seism and i >= 2 and signals[i-1] == 0 and signals[i-2] == 0:
               in_seism = True
               current_duration = 1
           elif in_seism:
               current_duration += 1
       else:
           if in_seism:
               if i+1 < n and signals[i+1] == 0:
                   total_seisms += 1
                   max_seism_duration = max(max_seism_duration, current_duration)
                   in_seism = False
                   current_duration = 0
   
   if in_seism:
       if n >= 2 and signals[n-1] == 0 and signals[n-2] == 0:
           total_seisms += 1
           max_seism_duration = max(max_seism_duration, current_duration)
   
   # Durata maximă a unui seism după modificare
   max_seism_after_modification = 0
   
   for i in range(n):
       if signals[i] == 0:
           modified_signals = signals[:i] + [1] * (n - i)
           current_duration = 0
           max_duration = 0
           in_seism = False
           
           for j in range(n):
               if modified_signals[j] == 1:
                   if not in_seism and j >= 2 and modified_signals[j-1] == 0 and modified_signals[j-2] == 0:
                       in_seism = True
                       current_duration = 1
                   elif in_seism:
                       current_duration += 1
               else:
                   if in_seism:
                       if j+1 < n and modified_signals[j+1] == 0:
                           max_duration = max(max_duration, current_duration)
                           in_seism = False
                           current_duration = 0
           
           if in_seism:
               if n >= 2 and modified_signals[n-1] == 0 and modified_signals[n-2] == 0:
                   max_duration = max(max_duration, current_duration)
           
           max_seism_after_modification = max(max_seism_after_modification, max_duration)
   
   return max_seism_duration, total_seisms, max_seism_after_modification

1. Exemplu de utilizare

signals = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0] max_seism_duration, total_seisms, max_seism_after_modification = analyze_seismic_data(signals) print("Durata maximă a unui seism:", max_seism_duration) print("Numărul total de seisme:", total_seisms) print("Durata maximă a unui seism după modificare:", max_seism_after_modification) </syntaxhighlight>