4054 - Seg Max

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

<syntaxhighlight lang="python" line>

1. 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].