4054 - Seg Max

From Bitnami MediaWiki

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>

  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[edit | edit source]

Segmentele de lungimi maxime sunt [6, 20], [11, 20], [0, 6], respectiv [15, 20].