4054 - Seg Max
De la Universitas MediaWiki
Cerința
Vom considera un segment pe axa Ox care începe la poziția 0 și se termină la poziția L.
Se vor insera pe rând N puncte pe axă, iar după fiecare punct inserat se va afișa lungimea celui mai lung segment delimitat de două puncte (inclusiv 0 și L).
Date de intrare
Programul citește de la tastatură numerele L și N, iar apoi N numere naturlae, reprezentând punctele care urmează să fie inserate.
Date de ieșire
Programul va afișa pe ecran N linii, a i-a linie reprezentând lungimea celui mai lung segment delimitat de două puncte, după inserarea celui de al i-lea punct.
Restricții și precizări
- 1 ≤ N ≤ 100 000
- 1 ≤ L ≤ 10**18
- Fiecare punct inserat se află în intervalul (0, L)
- Punctele inserate sunt distincte.
- Punctele 0 și L se consideră inserate de la început.
- În cadrul acestei probleme, vom defini lungimea unui segment ca fiind numărul de puncte cu coordonate numere naturale care se află pe segmentul dat.
Exemplul 1
- Intrare
- 20 4
- 6
- 11
- 15
- 4
- Ieșire
- 15
- 10
- 7
- 6
Exemplul 2
- Intare
- 30
- 5
- 10
- 25
- 5
- 20
- 15
- Iesire
- 30
- 30
- 30
- 25
- 25
Rezolvare
#4054 - Seg Max
def check_restrictions(L, N, points):
if not (1 <= N <= 100000 and 1 <= L <= 10**18):
return False
if len(points) != N:
return False
if not all(0 < point < L for point in points):
return False
return True
def main():
# Citirea datelor de intrare
L = int(input())
N = int(input())
points = [int(input()) for _ in range(N)]
# Verificarea restricțiilor
if not check_restrictions(L, N, points):
print("false")
return
# Inițializare variabile
sorted_points = [0, L] # Punctele sortate, începând cu 0 și L
lengths = [L] # Lungimile segmentelor după fiecare inserare
# Procesarea inserărilor
for point in points:
# Adăugăm noul punct în ordine
sorted_points.append(point)
sorted_points.sort()
# Recalculăm lungimile segmentelor
lengths.append(max(sorted_points[i + 1] - sorted_points[i] for i in range(len(sorted_points) - 1)))
# Afișarea rezultatelor
for length in lengths[1:]:
print(length)
if __name__ == "__main__":
main()
Explicatie
Segmentele de lungimi maxime sunt [6, 20], [11, 20], [0, 6], respectiv [15, 20].