3286 - Nr Not

Sursa: [1]

Cerinţa

Programul contine pe prima linie un număr natural n (n∈[2,107]) , iar pe următoarele linii un șir de cel mult 1000 numere naturale din intervalul [1,n]. Numerele sunt ordonate descrescător și sunt separate prin câte un spațiu. Se cere să se determine numărul valorilor naturale distincte din intervalul [1,n] care NU se găsesc în șir.

Date de intrare

Programul conține pe prima linie numărul n, iar pe următoarele linii numere naturale separate prin spații.

Date de ieșire

Programul va conține pe prima linie numărul k, reprezentând numărul de valori naturale distincte din intervalul [1,n] care nu se găsesc în șir.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează numărul valorilor naturale distincte din intervalul [1,n] care NU se găsesc în șir.

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

2 ≤ n ≤ 10.000.000

numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000

se recomandă evitarea memorării numerelor date într-un tablou sau în altă structură similară!

Exemplul 1

Datele de intrare

Numarul natural N ales,impreuna cu sirul ales sunt:

10

8 8 8 5 3 3

Datele de ieșire

Datele sunt introduse corect.

7

Rezolvare

#3286
def validate_input(n: int, nums: set[int]) -> bool:
    if n < 2 or n > 10000000:
        return False
    for num in nums:
        if num < 1 or num >= 10000000:
            return False
    return True

def find_remaining_numbers(n: int, nums: set[int]) -> int:
    for x in map(int, input().split()):
        nums.discard(x)

    return len(nums)

if __name__ == '__main__':
    n = int(input("Numarul natural N ales,impreuna cu sirul ales sunt:"))
    nums = set(range(1, n+1))

    if not validate_input(n, nums):
        print("Datele nu corespund restricțiilor impuse.")
    else:
        print("Datele sunt introduse corect.")
        remaining = find_remaining_numbers(n, nums)
        print(remaining)

Explicatie cod:

Funcția validate_input primește ca argumente un număr natural n și un set de numere nums, și returnează False dacă n nu este între 2 și 10.000.000, sau dacă oricare dintre numerele din setul nums nu se află între 1 și 10.000.000, altfel returnează True.

Funcția find_remaining_numbers primește ca argumente un număr natural n și un set de numere nums, citind apoi numere de la tastatură cu input().split() și eliminându-le pe rând din setul nums folosind metoda discard(). Funcția returnează numărul de elemente rămase în setul nums.

În funcția principală __main__, se citește de la tastatură numărul natural n și se construiește setul nums cu numerele de la 1 la n. Dacă argumentele primite nu sunt valide conform funcției validate_input, se afișează mesajul "Input invalid!". Altfel, se calculează numerele rămase în setul nums cu ajutorul funcției find_remaining_numbers și se afișează rezultatul.