1468 - Relativ

Sursa: [1]

Cerinţa

Se dă un şir format din n numere naturale. Un termen din şir se numeşte minim relativ dacă este mai mic sau egal decât toţi termenii din şir situaţi înaintea lui. Să se determine numărul elementelor din şir care sunt minime relative, precum şi suma maximă a elementelor dintr-o secvenţă cuprinsă între două minime relative consecutive, inclusiv acestea.

Date de intrare

Fișierul de intrare relativ.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire relativ.out va conține pe prima linie numărul k, reprezentând numărul termenilor din şir care sunt minime relative, iar pe a doua linie maximul sumei elementelor dintr-o secvenţă cuprinsă între două minime relative consecutive din şir, inclusiv acestea.

Restricţii şi precizări

• 1 ⩽ n ⩽ 1.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• o secvenţă cuprinsă între doi termeni din şir conţine toţi termenii din şir situaţi între aceştia, inclusiv cei doi termeni daţi.
• primul termen din şir este considerat minim relativ
• şirul conţine cel puţin doi termeni care sunt minime relative

Exemplul 1

Intrare

relativ.in

9

3

5

9

2

7

11

3

4

2

Ieșire

Datele introduse corespund cerintelor.

relativ.out

3

29

Exemplul 2

Intrare

relativ.in

0

3

5

9

2

7

11

3

4

2

Ieșire

Datele introduse nu corespund cerintelor.

Rezolvare

<syntaxhighlight lang="python" line>

1. 1468

def validate_input(n, numbers):

   if not 1 <= n <= 1000000:
       print("Datele introduse nu corespund cerintelor.")
       exit()
   if len(numbers) != n:
       print("Datele introduse nu corespund cerintelor.")
       exit()
   for num in numbers:
       if not 1 <= num <= 1000000000:
           print("Datele introduse nu corespund cerintelor.")
           exit()

def calculate_max_sum(numbers):

   cnt, minim = 0, 1000000001
   maxim, s = 0, 0
   for x in numbers:
       if x <= minim:
           if s + x > maxim:
               maxim = s + x
           cnt += 1
           minim = x
           s = x
       elif x > minim:
           s += x
   return cnt, maxim

def read_input_file(input_file):

   with open(input_file, 'r') as f_in:
       n = int(f_in.readline().strip())
       numbers = list(map(int, f_in.readlines()))
   return n, numbers

def write_output_file(output_file, cnt, maxim):

   with open(output_file, 'w') as f_out:
       f_out.write(str(cnt) + '\n')
       f_out.write(str(maxim) + '\n')

if __name__ == "__main__":

   input_file = 'relativ.in'
   output_file = 'relativ.out'
   n, numbers = read_input_file(input_file)
   validate_input(n, numbers)
   cnt, maxim = calculate_max_sum(numbers)
   print(f"Datele introduse corespund cerintelor.")
   write_output_file(output_file, cnt, maxim)

</syntaxhighlight>

Explicatie rezolvare

Acest program are rolul de a citi un fișier de intrare, procesa datele și scrie rezultatele într-un fișier de ieșire. Funcția validate_input verifică dacă datele de intrare respectă anumite condiții și afișează un mesaj de eroare în caz contrar. Funcția main deschide fișierele de intrare și de ieșire, citeste numărul de numere de la începutul fișierului de intrare și apoi citeste lista numerelor. După aceea, verifică datele de intrare utilizând funcția validate_input. Mai departe, procesează datele și scrie rezultatele în fișierul de ieșire.

Programul primește un fișier de intrare cu n numere întregi, apoi calculează câte dintre aceste numere sunt mai mici sau egale cu toate numerele anterioare din listă și determină suma maximă a acestor numere. Programul afișează numărul de astfel de numere și suma maximă găsită în fișierul de ieșire.