Fișierul intrare/ieșire divimax.in, divimax.out Sursă Olimpiada locala 2010, Clasa a 10-a
Autor Corina Ciobanu Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.05 sec Limită de memorie 1024 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Divimax

Având note mici la matematică, Gicuța primește spre rezolvare următoarea problemă (ușoară pentru clasa a X-a) pentru a-și mări nota: “Dându-se un șir X cu N numere naturale nenule: X1, X2,…., XN, să se determine cel mai mare divizor prim dintre toti divizorii tuturor numerelor din șirul X “.
Însă, pentru a obține nota 10, el mai are de rezolvat o cerință a problemei: să determine cel mai mare număr care se poate forma din concatenarea divizorilor primi maximi ai fiecărui număr din șirul X.

Cerință

Scrieți un program care să citească numărul natural N și cele N numere naturale din șirul X și care să determine:

  • numărul natural P reprezentând cel mai mare divizor prim dintre toți divizorii tuturor numerelor din șirul X ;
  • cel mai mare număr natural K ce se poate forma din concatenarea divizorilor primi maximi ai fiecărui număr din șirul X.

Date de intrare

Fisierul divimax.in conține N + 1 linii. Pe prima linie este scris numărul natural N, iar pe fiecare dintre următoarele N linii este scris câte un număr din șirului X, astfel încât pe linia i + 1 din fișier este scris numărul Xi.

Date de ieșire

Fișierul divimax.out va conține două linii. Pe prima linie se va scrie numărul natural P reprezentând cel mai mare divizor prim dintre toți divizorii tuturor numerelor din șirul X. Pe a doua linie a fișierului se va scrie numărul K, reprezentând cel mai mare număr natural ce se poate forma din concatenarea divizorilor primi maximi ai fiecărui număr din șirul X.

Restricții

  • 1 ≤ N ≤ 2000
  • 2 ≤ Xi ≤ 3500
  • Pentru 20% din teste 1 ≤ N ≤ 100, 2 ≤ Xi ≤ 2000
  • Pentru 50% din teste 1 ≤ N ≤ 1000, 2 ≤ Xi ≤ 3500
  • Concatenarea a două numere inseamnă lipirea lor. (exemplu: Prin concatenarea numerelor 325 și 684 rezultă numărul 325684, iar concatenându-le invers, obținem 684325)
  • Numărul determinat la cerința b) poate avea cel mult 8000 de cifre
  • Pentru rezolvarea corectă a cerinței a) se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinței b) se acordă 70% din punctaj

Exemplu

divimax.in divimax.out Explicatie
5
2
36
15
12
33
11
533211
Cel mai mare divizor prim al lui 2 este 2, cel mai mare divizor prim al lui 36 este 3,
cel mai mare divizor prim al lui 15 este 5, cel mai mare divizor prim al lui 12 este 3,
cel mai mare divizor al lui 33 este 11.
7
23
44
10
204
4
45
9
23
5532321711
Cei mai mari divizori primi ai numerelor sunt 23, 11, 5, 17, 2, 5, 3
(în ordinea în care sunt date în fișierul de intrare).

Trebuie să te autentifici pentru a trimite soluții. Click aici