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

<syntaxhighlight lang="python" line> 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()

</syntaxhighlight>

Explicatie

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