1596 - Divizori 1

Cerinţa

Fie X un vector de numere naturale distincte, de dimensiune N, X = (x[1], x[2], …, x[N]). Se dă un număr natural Q, apoi Q întrebări de forma: “Câţi divizori ai lui Qi se află în şirul X?”. Răspundeţi la cele Q întrebări.

Date de intrare

Fișierul de intrare divizori1in.txt conține:

• Pe prima linie 2 numere N și Q, reprezentând dimensiunea lui X şi numărul de întrebări;
• Pe a doua linie se găsesc N numere separate prin spaţiu, reprezentând elementele vectorului X.
• Pe următoarele Q linii se găsesc cele Q întrebări, reprezentate printr-un număr Qi pe fiecare linie.

Date de ieșire

Fișierul de ieșire divizori1out.txt va conține:

• Q linii, fiecare linie i, reprezentând răspunsul pentru Qi.

Restricţii şi precizări

• 1 ⩽ N, Q ⩽ 10.000
• 1 ⩽ Qi, Xi ⩽ 100.000

Exemplu 1

divizori1in.txt

5 2
6 2 3 12 4
6
12

divizori1out.txt

Datele de intrare corespund restrictiilor impuse
3
5

Exemplu 2

divizori1in.txt

5 2
6 2 3 12 4
6
123456

divizori1out.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

def validare(n, q, x, queries):
    if not n.isdigit() or int(n) < 1 or int(n) > 10000:
        return False, "Datele de intrare nu corespund restrictiilor impuse"

    if not q.isdigit() or int(q) < 1 or int(q) > 10000:
        return False, "Datele de intrare nu corespund restrictiilor impuse"

    for val in x:
        if not val.isdigit() or int(val) < 1 or int(val) > 100000:
            return False, "Datele de intrare nu corespund restrictiilor impuse"

    for val in queries:
        if not val.isdigit() or int(val) < 1 or int(val) > 100000:
            return False, "Datele de intrare nu corespund restrictiilor impuse"

    return True, "Datele de intrare corespund restrictiilor impuse"


def main():
    # Deschidem fișierul de intrare și citim datele
    with open('divizori1in.txt', 'r') as fin:
        n, q = fin.readline().split()
        x = fin.readline().split()
        queries = [line.strip() for line in fin.readlines()]

    valid, message = validare(n, q, x, queries)  # apelul functiei de validare
    with open('divizori1out.txt', 'w') as fout:
        fout.write(message + '\n')
        if not valid:
            return

    int(n), int(q)
    x = [int(val) for val in x]
    queries = [int(val) for val in queries]

    # Inițializăm lista de răspunsuri
    answers = []

    # Parcurgem fiecare întrebare
    for query in queries:
        # Calculăm numărul de divizori ai lui query care se află în x
        answer = sum(1 for xi in x if query % xi == 0)
        # Adăugăm răspunsul la lista de răspunsuri
        answers.append(answer)

    # Scriem răspunsurile în fișierul de ieșire
    with open('divizori1out.txt', 'a') as fout:
        for answer in answers:
            fout.write(str(answer) + '\n')


if __name__ == "__main__":
    main()

Explicatie

• 6 conţine 3 divizori în şir(6, 2, 3)
• 12 conţine 5 divizori în şir(6, 2, 3, 12, 4).