View source for 3939 - Intervale6

Sursa: [https://www.pbinfo.ro/probleme/3939/intervale6 - Intervale6]
----
== Cerinţa ==
Se dă un șir n numere naturale separate prin câte un spațiu.
Se cere să se afișeze numărul de intervale care nu conțin niciun termen al șirului.

== Date de intrare ==
Fișierul de intrare intervale6.in conține:
* pe prima linie un număr n.
* pe a doua linie un șir de n numere.
* iar pe fiecare dintre următoarele linii, până la finalul fișierului, câte o pereche de numere, reprezentând extremitățile unui interval închis.

== Date de ieșire == 
Fișierul de ieșire intervale6.out va conține:
Dacă datele sunt introduse corect, pe ecran se va afișa: 
'''"Datele sunt introduse corect."''', apoi pe un rând nou ''' umărul de intervale care nu conțin niciun termen al șirului aflat pe a doua linie a fișierului.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

== Restricţii şi precizări ==
* Fișierul intervale6.in conține numere naturale din intervalul [1, 10.000].
* Numerele aflate pe a doua linie a fișierului sunt în ordine crescătoare.
* Vor fi cel mult 200.000 de intervale
== Exemplu 1 ==
; Intrare
: intervale6.in
: 5
: 4 8 9 16 25
: 1 3
: 2 5
: 9 15
: 5 7
: 20 100
: 10 12
; Ieșire
: Datele sunt introduse correct.
: intervale6.out
: 3

== Exemplu 2 ==
; Intrare
: intervale6.in
: 2 1
: 1 2 3 4 8 9 16 25
: 2 6 
: 9 1
: 9 15
: 11 23
: 25 70
: 10 12
; Ieșire
: Datele nu corespund restricțiilor impuse.

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3939 - Intervale6

def validate_input(n, sir, intervale):
    if n < 1 or n > 10000:
        return False

    if len(sir) != n or any(sir[i] >= sir[i+1] for i in range(n-1)):
        return False

    if len(intervale) > 200000:
        return False

    return True


def numar_intervale(n, sir, intervale):
    if not validate_input(n, sir, intervale):
        return "Datele nu corespund restricțiilor impuse."

    termene_sir = set(sir)
    numar_intervale_fara_termene = 0

    for i, j in intervale:
        interval_are_termen = False
        for termen in sir:
            if i <= termen <= j:
                interval_are_termen = True
                break
        if not interval_are_termen:
            numar_intervale_fara_termene += 1

    return numar_intervale_fara_termene


if __name__ == "__main__":
    with open("intervale6.in", "r") as fin:
        n = int(fin.readline())
        sir = list(map(int, fin.readline().split()))
        intervale = []
        for line in fin.readlines():
            i, j = map(int, line.split())
            intervale.append((i, j))

    rezultat = numar_intervale(n, sir, intervale)

    if isinstance(rezultat, str):
        print(rezultat)
    else:
        print("Datele sunt introduse corect.")
        print(rezultat)



</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția validate_input(n, sir, intervale): Această funcție primește parametrii n, sir și intervale și are rolul de a valida datele de intrare conform restricțiilor impuse în cerință. Verificările includ:

Verifică dacă n se încadrează în intervalul permis (1 ≤ n ≤ 10,000).
Verifică dacă sir are lungimea n și este ordonat în mod crescător.
Verifică dacă numărul de intervale intervale este mai mic sau egal cu 200,000.
Funcția returnează True dacă datele sunt valide și False în caz contrar.

Funcția numar_intervale(n, sir, intervale): Această funcție primește datele de intrare n, sir și intervale și rezolvă problema în conformitate cu cerințele. Algoritmul funcției este următorul:

Verifică dacă datele de intrare sunt valide utilizând funcția validate_input. Dacă nu sunt valide, funcția returnează un mesaj de eroare.
Creează un set termene_sir care conține toate numerele din sir.
Inițializează variabila numar_intervale_fara_termene cu 0, care va reprezenta numărul de intervale care nu conțin niciun termen din sir.
Pentru fiecare interval din lista intervale, verifică dacă există cel puțin un termen din sir în interval. Dacă nu există, incrementăm numar_intervale_fara_termene.
Returnează numar_intervale_fara_termene.
Blocul if __name__ == "__main__": Acest bloc de cod verifică dacă scriptul Python este rulat direct (nu importat ca modul în alt script). În acest caz, citirea datelor de intrare se face din fișierul "intervale6.in" și se apelează funcția numar_intervale pentru a rezolva problema. Rezultatul este afișat în consolă.