4305 - Chimie 1

Cerinţa

Mateo este elev în clasa a 9-a și este pasionat atât de chimie cât și de informatică. El folosește de obicei două substanțe standard în cantități ce reprezintă două numere prime distincte, și a descoperit că anumite substanțe au în compoziție una sau chiar cele două substanțe standard în cantități ce reprezintă produsul cantităților celor două substanțe standard sau puteri ale acestora. El are în laborator un set de recipiente cu substanțe diferite și dorește să afle care este substanța de cantitate maximă care să aibă în componență una sau chiar cele două substanțe standard și de câte ori se regăsește această substanță de cantitate maximă. Pentru a-l ajuta pe Mateo căutați într-un sir de n numere cel mai mare element care are maximum doi divizori factori primi d1 si d2, reprezentând cele două substanțe standard și afișați de câte ori apare.

Date de intrare

Fișierul de intrare chimie1.in conține pe prima linie trei parametrii n, d1 și d2 cu semnificația din enunț, iar pe a doua linie n numere naturale separate prin spații.

Date de ieşire

Fișierul de ieșire chimie1.out va conține pe prima linie numărul m, reprezentând cel mai mare număr care respectă cerința și o variabilă ap care reprezintă numărul său de apariții. Dacă nu există niciun număr care respectă cerința se afișează mesajul NU EXISTA.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• 1 < d1 < d2 < 33.000
• numerele de pe a doua linie a fișierului de intrare sunt naturale și vor fi mai mici decât 33000

Exemplu

chimie1.in

6 5 7

4 35 5 175 23 175

chimie1.out

175 2

Explicație

175 este format din 5 la puterea 2 si 7 la puterea 1. Mai apar în șir numere care respectă cerința, dar 175 este cel mai mare.

Rezolvare

def validare_date(n, d1, d2, numere):
    return 1 <= n <= 1000000 and 1 < d1 < d2 < 33000 and all(numar < 33000 for numar in numere)

if __name__ == '__main__':
    # citire date din fisier
    with open('chimie1.in', 'r') as f:
        n, d1, d2 = map(int, f.readline().split())
        numere = list(map(int, f.readline().split()))

    # validare date
    if not validare_date(n, d1, d2, numere):
        print("Datele de intrare nu corespund restricțiilor impuse.")
        exit()

    # calculare rezultat
    numere_aparitii = {}
    for numar in numere:
        if numar % d1 == 0 or numar % d2 == 0:
            # numarul are unul dintre divizorii cautati
            factori = set()
            if numar % d1 == 0:
                factori.add(d1)
                numar //= d1
            if numar % d2 == 0:
                factori.add(d2)
                numar //= d2
            if numar == 1 and len(factori) <= 2:
                # numarul are maxim 2 factori primi si are cel putin unul dintre divizorii cautati
                numere_aparitii[numar] = numere_aparitii.get(numar, 0) + 1

    # afisare rezultat
    if not numere_aparitii:
        print("NU EXISTA")
    else:
        max_numar = max(numere_aparitii.keys())
        ap_max = numere_aparitii[max_numar]
        print(max_numar, ap_max)

Explicație rezolvare

În acest cod se caută cel mai mare număr dintr-o listă care are cel puțin unul dintre doi divizori specificați, iar acest număr trebuie să aibă cel mult doi factori primi. Se verifică în prealabil dacă datele de intrare corespund restricțiilor impuse, se trece prin toate numerele din listă și se verifică condiția impusă, iar la final se afișează rezultatul.