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
șiN - 4
secunde - Pentru cerințele
1
și2
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 în1
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.
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
# 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)