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

0

3

5

9

2

7

11

3

4

2

Ieșire

Input invalid: n trebuie să fie între 1 și 1.000.000.

Rezolvare

#1468
def validate_input(n, numbers):
    if not 1 <= n <= 1000000:
        print("Input invalid: n trebuie să fie între 1 și 1.000.000")
        exit()
    if len(numbers) != n:
        print("Input invalid: numărul de numere nu corespunde valorii lui n")
        exit()
    for num in numbers:
        if not 1 <= num <= 1000000000:
            print("Input invalid: numerele trebuie să fie între 1 și 1.000.000.000")
            exit()


def main(input_file, output_file):
    with open(input_file, 'r') as f_in, open(output_file, 'w') as f_out:
        n = int(f_in.readline().strip())
        numbers = list(map(int, f_in.readlines()))
        validate_input(n, 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
        f_out.write(str(cnt) + '\n')
        f_out.write(str(maxim) + '\n')


main('relativ.in', 'relativ.out')

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.