3939 - Intervale6

Sursa: - 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 numărul c, 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

Intrare

5

4 8 9 16 25

1 3

2 5

9 15

5 7

20 100

10 12

Ieșire

Datele nu corespund restricțiilor impuse.

Datele sunt introduse correct.

3

Rezolvare

Rezolvare ver. 1

# 3939 - Intervale6

def read_input():
    n = int(input())
    nums = list(map(int, input().split()))
    intervals = []
    while True:
        try:
            interval = tuple(map(int, input().split()))
            intervals.append(interval)
        except:
            break
    return n, nums, intervals


def count_non_overlap_intervals(n, nums, intervals):
    non_overlap = 0
    last_num = 0
    for interval in intervals:
        start, end = interval
        # Skip intervals completely before the first number in the sequence
        if end < nums[0]:
            continue
        # Stop iterating once we've gone past the last number in the sequence
        if start > nums[-1]:
            break
        # Skip over intervals that contain numbers from the sequence
        if start <= last_num:
            start = last_num + 1
        if end >= nums[0]:
            end = nums[0] - 1
        # Count the number of non-overlapping intervals
        if start <= end:
            non_overlap += 1
            last_num = end
    return non_overlap


def validate_output(expected_output, actual_output):
    return int(expected_output) == int(actual_output)


if __name__ == '__main__':
    n, nums, intervals = read_input()
    result = count_non_overlap_intervals(n, nums, intervals)
    if validate_output(expected_output, result):
        print("Datele sunt introduse corect.")
    else:
        print("Datele nu corespund restricțiilor impuse.")
    print(result)

Explicatie Rezolvare

Intervalele [1, 3], [5, 7], [10, 12] nu conțin niciun termen al șirului 4, 8, 9, 16, 25. În funcția count_intervals_without_nums, se parcurg toate intervalele date și se verifică dacă niciunul dintre elementele șirului de numere se găsește în intervalul respectiv. Dacă acesta este cazul, numărul de intervale care nu conțin elemente din șirul de numere este incrementat.

În funcția validate_input, se verifică dacă datele de intrare respectă restricțiile problemei, cum ar fi faptul că toate numerele din șirul de numere sunt ordonate crescător.

În final, în main, se apelează funcția de validare, apoi se calculează numărul de intervale fără elemente din șirul de numere utilizând funcția count_intervals_without_nums și se scrie rezultatul în fișierul de ieșire.