1735 - divquery

Cerința

Se dă un vector indexat de la 1 cu n elemente numere naturale. Să se răspundă la q întrebări de forma x y, cu semnificația: “Care este cel mai mare divizor comun al elementelor cu indici cuprinși între x și y, inclusiv?”

Date de intrare

Fișierul de intrare divquery.in conține pe prima linie numerele n și q, pe a doua linie cele n numere naturale ale vectorului, iar de la linia 3 începând, q linii, pe fiecare aflându-se doua numere x y, reprezentând întrebările.

Date de ieșire

Fișierul de ieșire divquery.out va conține q linii, pe fiecare linie i aflându-se răspunsul la întrebarea i. În consolă se va afișa un mesaj de validare a datelor "Datele de intrare sunt valide!" în acest caz. În caz contrar pe consolă se va afișa mesajul "Datele de intrare nu sunt valide!".

Restricții și precizări

1 ⩽ n ⩽ 100.000
1 ⩽ ai ⩽ 100.000
1 ⩽ q ⩽ 1.000.000

Exemplu

divquery.in

5 4; 1 3 18 2 3; 1 5; 2 3; 3 4; 2 4
divquery.out

1; 3; 2; 1
Consola: Datele de intrare sunt valide!

Explicație exemplu

În intervalul [1,5] cmmdc-ul este 1 În intervalul [2,3] cmmdc-ul este 3 În intervalul [3,4] cmmdc-ul este 2 În intervalul [2,4] cmmdc-ul este 1

Rezolvare

<syntaxhighlight lang="python"> def cmmdc(a, b):

   while b:
       r = a % b
       a = b
       b = r
   return a

def read_input(filename):

   with open(filename, 'r') as fin:
       n, q = map(int, fin.readline().split())
       a = list(map(int, fin.readline().split()))
       queries = []
       for _ in range(q):
           x, y = map(int, fin.readline().split())
           queries.append((x, y))
   return n, a, queries

def compute_logs(n):

   logs = [0] * (n+1)
   for i in range(2, n+1):
       logs[i] = 1 + logs[i//2]
   return logs

def compute_sparse_table(a):

   n = len(a)
   logs = compute_logs(n)
   st = [[0]*n for _ in range(logs[n]+1)]
   st[0] = a
   for i in range(1, logs[n]+1):
       for j in range(n-(1<<i)+1):
           st[i][j] = cmmdc(st[i-1][j], st[i-1][j+(1<<(i-1))])
   return st, logs

def process_queries(a, queries, st, logs):

   results = []
   for x, y in queries:
       dif = y - x + 1
       l = logs[dif]
       dif = dif - (1 << l)
       res = cmmdc(st[l][x-1], st[l][x-1+dif])
       results.append(res)
   return results

def write_output(filename, results):

   with open(filename, 'w') as fout:
       for res in results:
           fout.write(str(res) + '\n')

def validate_input(n, a, q):

   if not (1 <= n <= 100000):
       return False
   if not all(1 <= x <= 100000 for x in a):
       return False
   if not (1 <= x <= 1000000 for x in q):
       return False
   return True

if __name__ == '__main__':

   n, a, queries = read_input('divquery.in')
   if not validate_input(n, a, queries):
       print("Datele de intrare nu sunt valide!")
       return
   else:
       print("Datele de intrare sunt valide!")
   st, logs = compute_sparse_table(a)
   results = process_queries(a, queries, st, logs)
   write_output('divquery.out', results)

</syntaxhighlight>

Explicație cod

Acest cod este o implementare a unei soluții pentru problema "DivQuery", care se ocupă cu determinarea celui mai mare divizor comun dintr-un interval dat dintr-un șir de numere.

Funcția "cmmdc(a, b)" calculează cel mai mare divizor comun dintre două numere folosind algoritmul Euclid.

Funcția "read_input(filename)" citește datele de intrare dintr-un fișier și returnează numărul de elemente din șir (n), lista cu elementele (a) și o listă cu perechi de numere (queries), reprezentând intervalele pentru care trebuie calculat cel mai mare divizor comun.

Funcția "compute_logs(n)" calculează logaritmul în baza 2 pentru numerele de la 2 la n și returnează o listă cu valorile obținute. Aceste valori sunt utilizate pentru a determina numărul de niveluri din tabelul rar.

Funcția "compute_sparse_table(a)" construiește un tabel rar (sparse table) pentru șirul de numere dat (a). Tabelul este reprezentat ca o matrice (st) cu (logs[n]+1) niveluri și n coloane. Primul nivel al matricei conține elementele din șir, iar fiecare nivel următor se construiește pe baza nivelului precedent. Matricea este construită astfel încât pentru orice subinterval din șir se poate calcula cel mai mare divizor comun folosind două valori din tabelul rar.

Funcția "process_queries(a, queries, st, logs)" calculează cel mai mare divizor comun pentru fiecare interval din lista de intervale (queries) folosind tabela rară și returnează o listă cu rezultatele obținute.

Funcția "write_output(filename, results)" scrie rezultatele într-un fișier de ieșire.

Funcția "validate_input(n, a, q)" verifică dacă datele de intrare sunt valide, adică numărul de elemente din șir să fie între 1 și 100000, elementele din șir să fie între 1 și 100000, iar intervalele să fie între 1 și 1000000.

Blocul "if name == 'main':" este partea principală din cod care apelează celelalte funcții pentru a rezolva problema și afișează un mesaj de eroare în cazul în care datele de intrare nu sunt valide.