Oros Ioana Diana: Pagină nouă: == 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 p...

2024-01-08T19:22:14Z

Pagină nouă: == Cerința == Vom considera un segment pe axa Ox care începe la poziția 0 și se termină la poziția L. <br> 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 p...

New page

== Cerința ==
Vom considera un segment pe axa Ox care începe la poziția 0 și se termină la poziția L.
<br>
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
<br>
== Exemplul 2 ==
; Intare
: 30
: 5
: 10
: 25
: 5
: 20
: 15
; Iesire
: 30
: 30
: 30
: 25
: 25
<br>
== Rezolvare ==
<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 ==
Segmentele de lungimi maxime sunt [6, 20], [11, 20], [0, 6], respectiv [15, 20].

4054 - Seg Max - Revision history