4054 - Seg Max
Cerința[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
- 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[edit | edit source]
- Intrare
- 20 4
- 6
- 11
- 15
- 4
- Ieșire
- 15
- 10
- 7
- 6
Exemplul 2[edit | edit source]
- Intare
- 30
- 5
- 10
- 25
- 5
- 20
- 15
- Iesire
- 30
- 30
- 30
- 25
- 25
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line>
- 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()
</syntaxhighlight>
Explicatie[edit | edit source]
Segmentele de lungimi maxime sunt [6, 20], [11, 20], [0, 6], respectiv [15, 20].