4092 - cate

Cerința

Se dă "n", un număr natural și "n" perechi de numere ("a", "b"). Să se determine:

Câte numere din intervalul închis determinat de "a" și "b" au număr impar de divizori pozitivi. Câte numere cu exact trei divizori pozitivi se găsesc în intervalul închis determinat de "a" și "b".

Date de intrare

Fișierul de intrare "cate.in" conține pe prima linie două numere naturale "C" și "n", separate printr-un spațiu. "C" reprezintă cerința care trebuie rezolvată (1 sau 2), iar "n" reprezintă numărul de perechi. Pe următoarele "n" linii se găsesc cele "n" perechi de numere naturale, separate prin câte un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.". Fișierul de ieșire "cate.out" va conține "n" linii. Pe linia "i" trebuie să se găsească răspunsul la întrebarea corespunzătoare de pe linia "i+1" a fișierului de intrare. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ a, b ≤ 1.000.000
• Pentru 42 de puncte, C = 1
• Pentru 58 de puncte, C = 2

Exemple

Exemplul 1

cate.in

2 3

1 10

30 10

100 500

ecran

Datele sunt introduse corect.

cate.out

2

1

4

Exemplul 1

cate.in

1 3

1 10

30 10

100 500

ecran

Datele sunt introduse corect.

cate.out

3

2

13

Exemplul 3

cate.in

1 3

1 10

30 10

100 500000000

ecran

Datele nu corespund restricțiilor impuse.

cate.out

Rezolvare

# 4092 - cate
import sys
import math

def valideaza_datele(cerinta, numar_teste, teste):
    if cerinta not in [1, 2]:
        return "Datele nu corespund restricțiilor impuse."
    if numar_teste != len(teste):
        return "Datele nu corespund restricțiilor impuse."
    for test in teste:
        a, b = test
        if a < 1 or a > 1000000 or b < 1 or b > 1000000:
            return "Datele nu corespund restricțiilor impuse."
    return "Datele sunt introduse corect."

def rezolva_cerinta_1(teste):
    rezultate = []
    for test in teste:
        a, b = sorted(test)
        if a > b:
            rezultate.append(0)
        else:
            rezultate.append(int(math.sqrt(b)) - int(math.sqrt(a - 1)))
    return rezultate

def rezolva_cerinta_2(teste):
    numere_prime = [True] * 1000001
    numere_prime[0] = numere_prime[1] = False
    prefix_suma = [0] * 1000001
    for i in range(2, 1001):
        if numere_prime[i]:
            prefix_suma[i * i] = 1
            for j in range(i * i, 1000001, i):
                numere_prime[j] = False
    for i in range(1, 1000001):
        prefix_suma[i] += prefix_suma[i - 1]

    rezultate = []
    for test in teste:
        a, b = sorted(test)
        rezultate.append(prefix_suma[b] - prefix_suma[a - 1])
    return rezultate

if __name__ == '__main__':
    with open("cate.in", "r") as fisier_intrare:
        cerinta, numar_teste = map(int, fisier_intrare.readline().split())
        teste = []
        for _ in range(numar_teste):
            a, b = map(int, fisier_intrare.readline().split())
            teste.append((a, b))

    rezultat_validare = valideaza_datele(cerinta, numar_teste, teste)
    if rezultat_validare != "Datele sunt introduse corect.":
        print(rezultat_validare)
    else:
        if cerinta == 1:
            rezultate = rezolva_cerinta_1(teste)
        else:
            rezultate = rezolva_cerinta_2(teste)

        with open("cate.out", "w") as fisier_iesire:
            for rezultat in rezultate:
                fisier_iesire.write(str(rezultat) + "\n")
        print("Datele sunt introduse corect.")

Explicatie

valideaza_datele(cerinta, numar_teste, teste): Această funcție primește ca parametri cerința de rezolvat (cerinta), numărul de teste (numar_teste) și o listă de teste (teste). Ea verifică dacă datele introduse sunt valide conform cerințelor impuse. Mai întâi verifică dacă cerința este 1 sau 2 și apoi verifică dacă numărul de teste coincide cu numărul de teste introduse în listă. În cele din urmă, se verifică dacă valorile a și b din fiecare test sunt în intervalul [1, 1000000]. Dacă datele sunt introduse corect, funcția returnează un mesaj de confirmare, altfel returnează un mesaj de eroare.

rezolva_cerinta_1(teste): Această funcție primește ca parametru o listă de teste (teste) pentru cerința 1. Pentru fiecare test din listă, funcția sortează valorile a și b și calculează diferența dintre rădăcina pătrată a lui b și rădăcina pătrată a lui a-1. În cele din urmă, rezultatele sunt stocate într-o listă și returnate.

rezolva_cerinta_2(teste): Această funcție primește ca parametru o listă de teste (teste) pentru cerința 2. Funcția calculează, pentru fiecare număr între 2 și 1000000, dacă este prim sau nu. Această informație este stocată într-o listă de booleni numită numere_prime, în care valoarea True indică faptul că numărul este prim, iar valoarea False indică faptul că numărul nu este prim. De asemenea, funcția calculează un prefix-sum pentru această listă. Acest prefix-sum se numește prefix_suma și este folosit pentru a calcula rapid câte numere prime sunt într-un interval dat. Mai întâi, pentru fiecare pătrat al unui număr prim, se pune o valoare de 1 în prefix_suma, indicând faptul că acel număr prim se află în intervalul [pătratul lui i, 1000000]. Apoi, pentru fiecare număr între 1 și 1000000, se adaugă valoarea precedentă din prefix_suma la valoarea curentă, astfel încât prefix_suma devine un prefix-sum pentru numărul de numere prime din intervalul [1, i]. Pentru fiecare test din listă, funcția sortează valorile a și b și calculează diferența dintre prefix-suma lui b și prefix-suma lui a-1. În cele din urmă, rezultatele sunt stocate într-o lista

Funcția main este funcția principală a programului, care coordonează executarea acestuia. Ea verifică dacă programul este rulat ca script, sau este importat ca modul, prin intermediul instrucțiunii if __name__ == '__main__':.

Dacă programul este rulat ca script, atunci această instrucțiune va fi adevărată, iar codul din interiorul acesteia va fi executat. În acest caz, se deschide fișierul de intrare "cate.in" pentru citire, se citește prima linie pentru a obține cerința (cerinta) și numărul de teste (numar_teste), iar apoi se citește fiecare test și se stochează în lista teste. Aceste valori sunt folosite pentru a apela funcția valideaza_datele(cerinta, numar_teste, teste), care verifică dacă datele introduse sunt valide conform cerințelor impuse. Dacă datele sunt valide, atunci se apelează funcția corespunzătoare pentru a rezolva problema, fie rezolva_cerinta_1(teste) sau rezolva_cerinta_2(teste), în funcție de cerință. Rezultatele sunt stocate în lista rezultate, care este scrisă în fișierul de ieșire "cate.out", iar apoi se afișează un mesaj de confirmare a introducerii corecte a datelor.

Dacă programul este importat ca modul, atunci instrucțiunea if __name__ == '__main__': este falsă, iar codul din interiorul acesteia nu va fi executat. În acest caz, funcția main poate fi apelată din alt modul, pentru a rezolva problema cu datele date în parametrii funcției.