Fişierul intrare/ieşire:pyk.in, pyk.outSursăONI 2018 clasa a 5-a
AutorCarmen MincaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Pyk (clasa a 5-a)

Notă: enunţul problemei a fost modificat pentru a corespunde realităţii testelor. Punctajele au fost modificate pentru cele două cerinţe.

Fie k, n şi y trei numere naturale.

Fie X un şir format din n numere naturale: x1, x2, x3, ..., xn.

Fie P produsul numerelor y, x1, x2, x3, ..., xn , adică: P = y * x1 * x2 * x3 * ... * xn.

Numărul P este o "k-putere" dacă există un număr natural z astfel încât P = zk.

Cerinţe

Scrieţi un program care să citească numerele k, n, x1, x2, x3, ..., xn şi care să determine:

  1. cel mai mic număr şi cel mai mare număr din şirul X, formate doar din cifre identice;
  2. descompunerea în factori primi a celui mai mic număr natural y (y ≥ 2) cu proprietatea că numărul P = y * x1 * x2 * x3 * ... * xn este o "k-putere".

Date de intrare

Fişierul de intrare pyk.in conţine:

  • pe prima linie, un număr natural C reprezentând cerinţa din problemă care trebuie rezolvată (1 sau 2);
  • pe a doua linie, numerele naturale k şi n, separate printr-un singur spaţiu;
  • pe a treia linie, cele n numere naturale x1, x2, x3, ..., xn, separate prin câte un singur spaţiu.

Date de ieşire

Dacă C = 1, atunci prima linie a fişierului de ieşire pyk.out conţine două numere naturale, separate printr-un singur spaţiu, reprezentând răspunsul la cerinţa 1 a problemei. Dacă nu există astfel de numere, prima linie a fişierului va conţine valoarea 1.

Dacă C = 2, atunci fişierul de ieşire pyk.out conţine:

  • pe prima linie, un număr natural m reprezentând numărul de factori primi distincţi din descompunerea în factori primi a numărului y, determinat la rezolvarea cerinţei 2;
  • pe fiecare dintre următoarele m linii (câte o linie pentru fiecare factor prim din descompunerea în factori primi a lui y), câte două valori F şi E, separate printr-un singur spaţiu, reprezentând factorul prim F şi exponentul E al acestui factor din descompunerea în factori primi a lui y.

Scrierea în fişier a acestor factori primi se va face în ordinea crescătoare a valorii lor.

Restricţii

  • 2 ≤ n ≤ 50 000
  • 2 ≤ k ≤ 100
  • 2 ≤ x1, x2, x3, ..., xn ≤ 10 000
  • 2 ≤ y
  • pentru rezolvarea corectă a cerinţei 1 se acordă 10 15 puncte
  • pentru rezolvarea corectă a cerinţei 2 se acordă 90 85 de puncte.

Exemplu

pyk.inpyk.outExplicaţie
1
2 7
122 1111 5 4 88 123 999
4 1111
Cerinţa este 1, k = 2, n = 7.
Numerele din şirul X formate doar din cifre identice sunt:
1111, 5, 4, 88, 999. Cel mai mic număr dintre acestea este
4, iar cel mai mare este 1111.
2
3 6
12 5 60 125 4 36
3
2 1
3 2
5 1
Cerinţa este 2, k = 3, n = 6. Produsul celor 6 numere din şir
este: 12 * 5 * 60 * 125 * 4 * 36 = 64800000
y = 90  este cea mai mică valoare pentru care
P = 90 * 64800000 = 18003 devine o "k-putere".
Descompunerea în factori primi a lui y conţine m = 3 factori
primi: 21 * 32 * 51
Trebuie sa te autentifici pentru a trimite solutii. Click aici