3345 - Divimax

Enunț

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: X 1 , X 2,…., X N, 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ța

Scrieţi un program care să citească numărul natural N şi cele N numere naturale din şirul X şi care să determine: 1. numărul natural P reprezentând cel mai mare divizor prim dintre toţi divizorii tuturor numerelor din şirul X 2. 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

Fișierul de intrare divimax.in conține conţine N+1 linii. Pe prima linie sunt scrise doua numere naturale C și N, separate printr-un spațiu. 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 (1≤i≤N).

Date de ieșire

Fișierul de ieșire divimax.out va conține o linie. - Dacă C=1, atunci se va rezolva doar cerința 1 a problemei, iar pe prima linie se va scrie numărul natural P reprezentând raspunsul la cerința 1. - Dacă C=2, atunci se va rezolva doar cerința 2 a problemei, iar pe prima linie a fişierului se va scrie numărul natural K, reprezentând răspunsul la cerința 2.

Restricții și precizări

• 0 ≤ N ≤ 3030, N număr natural
• C=1 sau C=2
• 2 ≤ Xi ≤ 3500, unde 1 ≤ i ≤N
• 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 2 poate avea cel mult 8000 de cifre
• Pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.

Exemplul 1

divimax.in

1 5

2

36

15

12

33

divimax.out

11

Explicație

C=1, se va rezolva doar cerinta 1. 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.

Exemplul 2

divimax.in

3 3

8

8

4000

divimax.out

Date de intrare invalide!

Rezolvare

#3345 divimax
def este_prim(numar):
  if numar < 2:
    return False
  for i in range(2, int(numar ** 0.5) + 1):
    if numar % i == 0:
      return False
  return True

def determina_divizori(numar):
  divizori = []
  for i in range(1, numar + 1):
    if numar % i == 0:
      divizori.append(i)
  return divizori

def determina_cel_mai_mare_divizor_prim(lista_numere):
  divizori_prim = []
  for numar in lista_numere:
    divizori = determina_divizori(numar)
    for divizor in divizori:
      if este_prim(divizor):
        divizori_prim.append(divizor)
  return max(divizori_prim)

def determina_cel_mai_mare_numar_concatenare(lista_numere):
  divizori_prim = []
  for numar in lista_numere:
    divizori = determina_divizori(numar)
    for divizor in divizori:
      if este_prim(divizor):
        divizori_prim.append(divizor)
  divizori_prim.sort(reverse=True)
  return int(''.join(map(str, divizori_prim)))

def verifica_date_intrare(C, N, numere):
  if C not in [1, 2]:
    return False
  if not (0 <= N <= 3030):
    return False
  for numar in numere:
    if not (2 <= numar <= 3500):
      return False
  return True

def main():
  # Citire date de intrare
  with open('divimax.in', 'r') as f:
    C, N = map(int, f.readline().split())
    numere = [int(f.readline()) for _ in range(N)]

  # Verificare date de intrare
  if not verifica_date_intrare(C, N, numere):
    # Scriere mesaj de date invalide in fisierul de iesire
    with open('divimax.out', 'w') as fout:
      fout.write("Date de intrare invalide!")
    return

  # Calculare rezultat in functie de C
  if C == 1:
    P = determina_cel_mai_mare_divizor_prim(numere)
    rezultat = P
  elif C == 2:
    K = determina_cel_mai_mare_numar_concatenare(numere)
    rezultat = K

  # Scriere rezultat in fisierul de iesire
  with open('divimax.out', 'w') as f:
    f.write(str(rezultat) + '\n')

if __name__ == "__main__":
  main()