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

În cazul in care datele sunt introduse corect in consolă se va afișa mesajul "Datele introduse corespund cerintelor" și 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. În caz contrar programul va afișa în consolă mesajul "Datele introduse nu corespund cerintelor."

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

#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)

Explicatie rezolvare

În primul rând, există o funcție "validate_input" care verifică dacă datele de intrare sunt valide. Dacă nu sunt valide, se afișează un mesaj de eroare și programul se oprește. În caz contrar, programul continuă cu prelucrarea datelor de intrare.

În continuare, există o funcție "calculate_max_sum" care primește o listă de numere și calculează suma maximă a unei secvențe de numere care începe cu primul element și conține numai elemente care sunt mai mari sau egale cu cel anterior. În plus, calculează și lungimea acestei secvențe.

Funcția "read_input_file" citește datele de intrare dintr-un fișier și returnează valorile corespunzătoare. Funcția "write_output_file" scrie rezultatele într-un fișier de ieșire.

În funcția "main", datele de intrare sunt citite din fișierul "relativ.in" și verificate prin apelul funcției "validate_input". Apoi, se calculează suma maximă și lungimea secvenței prin apelul funcției "calculate_max_sum". În cele din urmă, se afișează un mesaj care confirmă că datele de intrare sunt valide și se scriu rezultatele în fișierul "relativ.out".