2433 - Cufar

Cerința

Vrăjitoarea cea bună are un cufăr în care este închisă piatra magică de către piticii lăzii cu ajutorul unui cifru digital. Piticii i-au dat vrăjitoarei o cutie în care sunt n cartonașe. Pe fiecare cartonaș este scris un număr natural pe care vrăjitoarea îl va folosi să deschidă lada. Valorile scrise pe cartonașe sunt distincte între ele.

Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaș din cutie și apoi determină valoarea magică asociată numărului natural scris pe cartonaș. Pentru fiecare cartonaș valoarea magică este dată de al k-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obținute pentru cele n cartonașe și apoi să introducă în ordine cifrele valorii obținute, pentru a descuia lada.

Deoarece vrăjitoarea nu are timp la dispoziție vă roagă pe voi să o ajutați să rezolve următoarele probleme:

1. Să afle valoarea magică pentru un cartonaș dat;

2. Să afle cifrul cufărului.

Date de intrare

Fișierul de intrare este cufar.in. Pe prima linie a fișierului de intrare se găsesc o valoare p care poate fi doar 1 sau 2 și numărul n de cartonașe despărțite prin câte un spațiu.

Dacă p este 1 pe linia a doua a fișierului de intrare se găsesc două valori reprezentând numărul de pe cartonașul dat și valoarea k, separate printr-un spațiu, cu semnificația de mai sus.

Dacă p este 2 pe următoarele n linii ale fișierului de intrare se găsesc câte două valori, separate prin câte un spațiu, reprezentând numărul de pe cartonaș și valoarea lui k pentru fiecare din cele n cartonașe.

Date de ieșire

Fișierul de ieșire este cufar.out. Dacă valoarea lui p este 1, atunci se va rezolva doar cerința 1 și fișierul de ieșire va conține pe prima linie valoarea magică asociată cartonașului dat.

Dacă valoarea lui p este 2, atunci se va rezolva doar cerința 2 și fișierul de ieșire va conține pe prima linie cifrul necesar deschiderii cufărului.

Restricții și precizări

• 1 ≤ n < 1 000 000
• 2 ≤ valoarea înscrisă pe un cartonaș ≤ 1 000 000

• Se garantează că pentru fiecare pereche (număr, k), număr are cel puțin k divizori primi.

Exemplu 1

Intrare

1 1

30 3

Ieșire

5

Explicație

p = 1, n = 1

Se rezolvă doar prima cerință. Al treilea divizor prim al numărului 30 este 5.

Exemplu 2

Intrare

2 5

30 3

64 1

105 2

1001 3

5474 4

Ieșire

48

Explicație

p = 2, n = 5

Se rezolvă doar a doua cerință. Al treilea divizor prim al numărului 30 este 5.

Primul divizor prim al numărului 64 este 2.

Al doilea divizor prim al numărului 105 este 5.

Al treilea divizor prim al numărului 1001 este 13.

Al patrulea divizor prim al numărului 5474 este 23.

Suma căutată va fi S = 5 + 2 + 5 + 13 + 23, de unde rezultă cifrul 48.

Exemplu 3

Intrare

2 3

1 3

1000000 1

Ieșire

Date de intrare gresite!

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 2433 Cufar

def prim(nr):

   if nr < 2:
       return False
   for i in range(2, int(nr**0.5) + 1):
       if nr % i == 0:
           return False

   return True

def valoare_magica(n, k) -> int:

   nr = 0

   for i in range(2, n+1):
       if n % i == 0 and prim(i):
           nr += 1
           if nr == k:
               return i

   return nr

def conditie_n(n):

   return 1 <= n < 1_000_000

def conditie_cartonas(cartonas):

   return 2 <= cartonas < 1_000_000

def main():

   p, n = [int(x) for x in input().split()]

   if not conditie_n(n):
       return print("Date de intrare gresite!")

   suma = 0
   for i in range(n):
       cartonas, k = [int(x) for x in input().split()]
       if not conditie_cartonas(cartonas):
           return print("Date de intrare gresite!")
       suma += valoare_magica(cartonas, k)

   print(suma)

if __name__ == "__main__":

   main()

</syntaxhighlight>