Fişierul intrare/ieşire:cufar.in, cufar.outSursăOJI 2018, Clasa a 9-a
AutorCristian TonceaAdăugată deAndrei1998Constantinescu Andrei-Costin Andrei1998
Timp execuţie pe test1.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cufar

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.

Cerinţă

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

  • 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.
  • Pentru rezolvarea corectă a cerinţei 1 se acordă 18 puncte
  • Pentru rezolvarea corectă a cerinţei 2 se acordă 72 de puncte
  • Pentru rezultate corecte la cerinţa a doua respectând restricţiile problemei şi n ≤ 1 000 se acordă 18 puncte
  • Pentru rezultate corecte la cerinţa a doua respectând restricţiile problemei şi n ≤ 500 000 se acordă 43 de puncte
  • Conform regulamentului OJI, se vor acorda 10 puncte din oficiu (pentru rezolvarea exemplelor).

Exemplu

cufar.incufar.outExplicaţie
1 1
30 3
5
p = 1, n = 1
Se rezolvă doar prima cerinţă.
Al 3-lea divizor prim al numărului 30 este 5.
2 5
30 3
64 1
105 2
1001 3
5474 4
48
p = 2, n = 5
Se rezolvă doar a doua cerinţă.
Al 3-lea divizor prim al numărului 30 este 5.
Primul divizor prim al numărului 64 este 2.
Al 2-lea divizor prim al numărului 105 este 5.
Al 3-lea divizor prim al numărului 1001 este 13.
Al 4-lea divizor prim al numărului 5474 este 23.
Suma căutată va fi S = 5 + 2 + 5 + 13 + 23, de unde rezultă cifrul 48.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?