2351 - Numere 23

Cerința

Se numește număr 3-prim, un număr natural care se poate descompune în produs de cel mult 3 numere prime, nu neapărat distincte. Cunoscând numerele naturale n și k, construiți un șir format din primele n numere 3-prime. Ordinea numerelor în șir va fi stabilită astfel încât, extrăgând pe rând numerele din șir, începând cu primul număr și apoi câte un număr din k în k poziții, circular, să obținem în ordine crescătoare, șirul primelor n numere 3-prime. Parcurgerea circulară înseamnă că după elementul aflat în vector pe locul n, urmează elementul de pe locul 1.

Cunoscând numerele n, k și c (c = 1 sau c = 2), se cere:

1. dacă c = 1, să se afișeze cel mai mare din cele n numere 3-prime.

2. dacă c = 2, să se construiască șirul de n numere care îndeplinește condiția din enunț.

Date de intrare

Fișierul de intrare numere23.in conţine pe prima linie, despărțite prin câte un spațiu, numerele naturale n, k și c, cu semnificaţia din enunţ.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Dacă c = 1, atunci pe următorul rând se va afișa un singur număr ce reprezintă cel mai mare din cele n numere 3-prime. Dacă c = 2, atunci se vor afișa despărțite prin câte un spațiu, șirul celor n numere 3-prime.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

0 < k < n ≤ 10000

numerotarea elementelor în vector se face de la 1

Exemplu 1

Intrare: 5 3 2
Ieșire: Datele de intrare corespund restricțiilor impuse.; 2 6 4 3 5

Explicație

Primele cinci numere 3-prime sunt: 2, 3, 4, 5, și 6. Șirul de numere 2, 6, 4, 3, 5 parcurs din 3 în 3, va forma în ordine crescătoare șirul de numere inițial.

Exemplu 2

Intrare: 10 4 2
Ieșire: Datele de intrare corespund restricțiilor impuse.; 2 11 10 5 3 8 7 9 4 6

Explicație

Primele 10 numere 3-prime sunt: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Șirul de numere 2, 11, 10, 5, 3, 8, 7, 9, 4, 6, parcurs din 4 în 4, va forma în ordine crescătoare șirul de numere inițial.

Exemplu 3

Intrare: 5 3 1
Ieșire: Datele de intrare corespund restricțiilor impuse.; 6

Explicație

Primele 10 numere 3-prime sunt: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Șirul de numere 2, 11, 10, 5, 3, 8, 7, 9, 4, 6, parcurs din 4 în 4, va forma în ordine crescătoare șirul de numere inițial.

Exemplu 4

Intrare: 3 10 1
Ieșire: Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

2351 Numere 23

def conditii(k, n):

   return 0 < k < n <= 10_000

def prim3(n):

   # Dacă n este mai mic decât 2, nu este 3-prim
   if n < 2:
       return False

   divizor, nr_factori_primi = 2, 0
   # Cât timp n este mai mare decât 1 și nu am găsit 3 factori primi:
   while n != 1 and nr_factori_primi <= 3:
       # Cât timp n este divizibil cu divizorul curent și nu am găsit 3 factori primi:
       while n % divizor == 0 and nr_factori_primi <= 3:
           # Împărțim n la divizorul curent și creștem numărul de factori primi găsiți
           n //= divizor
           nr_factori_primi += 1
       # Trecem la următorul divizor
       divizor += 1

   # Dacă n este 1 și am găsit 3 factori primi, n este 3-prim
   if n == 1 and nr_factori_primi <= 3:
       return True

   return False

def cel_mai_mare(n):

   rezultat = 1
   # Cât timp n este nenul:
   while n > 0:
       # Creștem rezultatul până când găsim un număr 3-prim
       rezultat += 1
       # Dacă rezultatul este 3-prim, scădem 1 din n
       if prim3(rezultat):
           n -= 1

   return rezultat

def sir_circular(n, k):

   val, poz, nr_n = 1, 1, n
   # Găsim cel mai mic număr 3-prim și îl asignăm pe prima poziție din vector
   while not prim3(val):
       val += 1
   vector = [0] * (n + 1)
   vector[1] = val
   nr_n -= 1

   # Continuăm să adăugăm numere 3-prime în vector până când vectorul conține n numere
   while nr_n > 0:
       # Căutăm următorul număr 3-prim și îl asignăm pe poziția curentă din vector
       val += 1
       while not prim3(val):
           val += 1

       # Trecem la următoarea poziție liberă din vector
       nr_k = k
       while nr_k > 0:
           poz += 1
           if poz > n:
               poz = poz % n
           if vector[poz] == 0:
               nr_k -= 1

       # Asignăm numărul 3-prim curent pe poziția curentă din vector
       vector[poz] = val
       nr_n -= 1
   
   # Returnăm numerele din vector separate prin câte un spațiu
   return " ".join(str(x) for x in vector[1:])

def numere23(c, n, k):

   # c este cerința enunțului
   if c == 1:
       print(cel_mai_mare(n))
   elif c == 2:
       print(sir_circular(n, k))

if __name__ == "__main__":

   n, k, c = map(int, input().split())

   if not conditii(k, n):
       print("Datele de intrare nu corespund restricțiilor impuse.")
   else:
       print("Datele de intrare corespund restricțiilor impuse.")
       numere23(c, n, k)

</syntaxhighlight>