2905 - Divizori 4

Cerinţa

Gigel a găsit un șir cu n numere naturale, numerotate de la 1 la n și un număr p. Neavând chef de muncă, Gigel vă cere să rezolvați următoarele cerințe:

a) Aflați câți divizori are numărul din șir aflat pe poziția p. b) Afișați în ordine descrescătoare numerele din șir care au același număr de divizori ca cel aflat pe poziția p.

Date de intrare

Fișierul de intrare divizori4in.txt conține pe prima linie numerele n c, unde c poate fi doar 1 sau 2. A doua linie conține cele n elemente ale șirului. A treia linie conține numărul p.

Date de ieşire

Dacă c=1 se rezolvă numai cerința a). Fișierul de ieșire divizori4out.txt va conține pe prima linie numărul de divizori ai numărului aflat în șir pe poziția p.

Dacă c=2 se rezolvă numai cerința b). Fișierul de ieșire divizori4out.txt va conține pe prima linie, în ordine descrescătoare, numerele din șir cu același număr de divizori ca și cel aflat pe poziția p.

Restricții și precizări

• numerele din șir vor fi numere naturale nenule mai mici sau egale cu 1.000.000.000
• pentru 50% din punctaj c=1; pentru 50% din punctaj c=2;
• pentru c=1, 1 ≤ p ≤ n ≤ 50.000
• pentru c=2, 1 ≤ p ≤ n ≤ 50.000 pentru 30% din punctaj și 1 ≤ p ≤ n ≤ 10.000 pentru 20% din punctaj

Exemplul 1

divizori4in.txt

10 1

1 5 95 23 16 39 77 74 97 57

3

divizori4out.txt

Datele introduse corespund restricțiilor impuse.

4

Explicație

c=1, se rezolvă doar cerința a). Al treilea număr din șir este 95, care are 4 divizori (1 5 19 95).

Exemplul 2

divizori4in.txt

10 2

1 5 95 23 16 39 77 74 97 57

3

divizori4out.txt

Datele introduse corespund restricțiilor impuse.

95 77 74 57 39

Explicație

c=2, se rezolvă doar cerința b). Al treilea număr din șir este 95, care are 4 divizori. Numerele cu 4 divizori din șir sunt, în ordine descrescătoare: 95 77 74 57 39.

Exemplul 3

divizori4in.txt

10 1

1 2 3 4 5 6 7 8 9 1000000001

5

divizori4out.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 2905 - Divizori 4

def validare(serie_validare):

   # Verificam daca numarul de elemente din serie este mai mare decat 50_000
   # Daca este, aruncam o exceptie ValueError
   if len(serie_validare) > 50_000:
       raise ValueError

   for numar in serie_validare:
       if not (1 <= numar <= 1_000_000_000):
           raise ValueError

   # Daca datele de intrare sunt valide, afisam un mesaj in fisierul de iesire
   fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")

def numar_divizori(n_divizori):

   i = 1
   rezultat = 0
   # Parcurgem numerele de la 1 la radacina patrata a numarului
   while i * i <= n_divizori:
       # Daca numarul nu este divizor, incrementam i
       if n_divizori % i:
           i += 1
           continue
       # Daca i este divizor, il adaugam la rezultat
       # Daca i * i este egal cu numarul, adaugam doar o data i la rezultat
       # Altfel, adaugam si i si numarul / i la rezultat
       if i * i == n_divizori:
           rezultat += 1
       else:
           rezultat += 2
       i += 1
   return rezultat

def divizori4(serie_divizori4, pozitie_divizori4, cerinta_divizori4):

   # Luam numarul de pe pozitia data
   numar = serie_divizori4[pozitie_divizori4-1]
   # Calculam numarul de divizori ai numarului
   divizori_numar = numar_divizori(numar)

   # Daca cerinta este 1, afisam numarul de divizori al numarului
   if cerinta_divizori4 == 1:
       fisier_iesire.write(str(divizori_numar))
   else:
       # Daca cerinta este 2, afisam numerele din serie care au acelasi numar de divizori ca numarul de pe pozitia data
       numere_cu_acelasi_nr_divizori = [x for x in serie_divizori4 if numar_divizori(x) == divizori_numar]
       # Sortam numerele in ordine descrescatoare
       numere_cu_acelasi_nr_divizori.sort(reverse=True)
       # Afisam numerele
       fisier_iesire.write(' '.join(map(str, numere_cu_acelasi_nr_divizori)))

if __name__ == '__main__':

   # Deschidem fisierele de intrare si iesire
   fisier_intrare = open("divizori4in.txt", "r")
   fisier_iesire = open("divizori4out.txt", "w")

   try:
       n_main, cerinta_main = map(int, fisier_intrare.readline().split())
       serie_main = list(map(int, fisier_intrare.readline().split()))
       pozitie_main = int(fisier_intrare.readline())

       # Validam datele de intrare
       validare(serie_main)
       # Rezolvam problema
       divizori4(serie_main, pozitie_main, cerinta_main)

   # Tratam exceptiile care pot aparea
   except ValueError:
       fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>