3738 - New York

Cerința

Doru s-a mutat în New York și își caută o nouă locuință specială în perimetrul străzilor numerotate cu numerele distincte de la 1 la n. Fiind pasionat de matematică, el vrea să se mute pe strada în care cel mai mare divizor comun (cmmdc) al înălțimilor clădirilor este maxim.

În plus, alegerea clădirii nu este una ușoară, el dorind să se mute doar într-o clădire perfectă. Numim o clădire perfectă o clădire care are cea mai mare înălțime număr prim de pe strada pe care se află.

Fiind ocupat cu împachetatul, Doru vă roagă pe voi să găsiți clădirea perfectă.

Date de intrare

Fișierul de intrare nykin.txt conține pe prima linie numărul de străzi n pe care Doru își caută noua locuință. Pe fiecare dintre următoarele n linii (câte una pentru fiecare stradă din cele n, în ordinea crescătoare a numerelor străzilor) se află numărul m, reprezentând numărul de clădiri de pe strada curentă, urmat de m numere ce reprezintă înălțimile clădirilor de pe strada curentă (în ordinea poziționării lor pe stradă, de la stânga la dreapta). Pe fiecare linie numerele sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire nykout.txt va conține două linii.

Prima linie va conține două numere naturale separate printr-un spațiu, reprezentând numărul străzii cerute și poziția pe stradă a clădirii în care se va muta Doru.

A doua linie va conține un număr natural reprezentând înălțimea clădirii alese.

Dacă pe strada cu cmmdc-ul maxim nu se găsește nicio clădire cu înălțimea un număr prim, atunci prima linie a fișierului va conține mesajul Nu am gasit casa!

Restricții și precizări

• 1 ⩽ n ⩽ 1000
• 1 ⩽ m ⩽ 1000
• Numerele de pe a doua linie a fișierului de intrare sunt mai mici decât 1 000 000 000
• Înălțimile clădirilor sunt numere naturale nenule mai mici ca 2 000 000 000.
• Pe fiecare stradă există cel puțin o clădire.
• Dacă pe strada cu cmmdc-ul maxim sunt mai multe clădiri perfecte, se va afișa cea mai din dreapta.
• Dacă sunt mai multe străzi cu aceeași clădire perfectă, se va afișa cea care are numărul străzii cel mai mare.

Exemplu 1

nykin.txt

5

2 1 2

3 18 6 48

2 5 7

4 3 6 9 12

4 34 17 68 17

nykout.txt

5 4

17

Explicatie

Valoarea maximă a celui mai mare divizor comun al înălțimilor clădirilor de pe o stradă dintre cele cinci este 17 (cmmdc(1,2)=1, cmmdc(18, 6, 48)=6, cmmdc(5, 7)=1, cmmdc(3, 6, 9, 12)=3, cmmdc(34, 17, 68, 17)=17). Astfel Doru va alege clădirea a 4-a de pe strada cu numărul 5.

Exemplu 2

nykin.txt

0

-1 -3

nykut.txt

Nu am gasit casa!

Rezolvare

#3738 - New York
def cmmdc_lista(lista):
    def cmmdc(a, b):
        while b:
            a, b = b, a % b
        return a

    result = lista[0]
    for elem in lista[1:]:
        result = cmmdc(result, elem)

    return result

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 gaseste_cladire_perfecta(strazi):
    cmmdc_maxim = 0
    strada_aleasa = 0
    cladire_aleasa = 0

    for i, strada in enumerate(strazi, start=1):
        inaltimi = strada[1:]
        cmmdc_strada = cmmdc_lista(inaltimi)

        if cmmdc_strada > cmmdc_maxim:
            cmmdc_maxim = cmmdc_strada
            strada_aleasa = i

            for j, inaltime in enumerate(reversed(inaltimi), start=1):
                if este_prim(inaltime):
                    cladire_aleasa = len(inaltimi) - j + 1
                    break

    return strada_aleasa, cladire_aleasa

try:
    # Citirea datelor de intrare
    with open('nykin.txt', 'r') as f:
        n = int(f.readline().strip())
        strazi = [list(map(int, f.readline().split())) for _ in range(n)]

    # Calculul și scrierea rezultatului în fișierul de ieșire
    rezultat = gaseste_cladire_perfecta(strazi)
    with open('nykout.txt', 'w') as g:
        if rezultat[0] == 0:
            g.write("Nu am gasit casa!")
        else:
            g.write(f"{rezultat[0]} {rezultat[1]}\n{strazi[rezultat[0] - 1][rezultat[1]]}")
except Exception as e:
    print("A aparut o eroare:", str(e))