1735 - divquery - Revision history

Monica Dragos: /* Date de ieșire */

2023-05-04T20:46:57Z

Date de ieșire

← Older revision		Revision as of 20:46, 4 May 2023
Line 6:		Line 6:

	==Date de ieșire==		==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!" ~~sau~~ "Datele de intrare nu sunt valide!" ~~după caz)~~.		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==		==Restricții și precizări==

Cata at 06:54, 3 May 2023

2023-05-03T06:54:54Z

← Older revision		Revision as of 06:54, 3 May 2023
Line 6:		Line 6:

	==Date de ieșire==		==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.		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!" sau "Datele de intrare nu sunt valide!" după caz).

	==Restricții și precizări==		==Restricții și precizări==
Line 29:		Line 29:
	; Consola		; Consola
	: Datele de intrare sunt valide!		: Datele de intrare sunt valide!
	==Explicație==		==Explicație exemplu==
	În intervalul [1,5] cmmdc-ul este 1		În intervalul [1,5] cmmdc-ul este 1
	În intervalul [2,3] cmmdc-ul este 3		În intervalul [2,3] cmmdc-ul este 3
Line 94:		Line 94:
	return True		return True

	~~def main()~~:		if __name__ == '__main__':
	n, a, queries = read_input('divquery.in')		n, a, queries = read_input('divquery.in')
	if not validate_input(n, a, queries):		if not validate_input(n, a, queries):
Line 105:		Line 105:
	write_output('divquery.out', results)		write_output('divquery.out', results)

	~~if __name__ == '__main__':~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>
Line 127:		Line 126:
	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.		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.

	~~Funcția~~ "main()" este ~~funcția~~ principală 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.		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.

	~~În final, condiția "if name == 'main':" verifică dacă codul este rulat ca script și apelează funcția principală~~.

Cata: /* Date de ieșire */

2023-04-28T07:59:05Z

Date de ieșire

← Older revision		Revision as of 07:59, 28 April 2023
Line 6:		Line 6:

	==Date de ieșire==		==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.		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.

	==Restricții și precizări==		==Restricții și precizări==

Cata at 07:58, 28 April 2023

2023-04-28T07:58:48Z

← Older revision		Revision as of 07:58, 28 April 2023
Line 13:		Line 13:
	* 1 &les; q &les; 1.000.000		* 1 &les; q &les; 1.000.000
	==Exemplu==		==Exemplu==
	divquery.in		; divquery.in

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

	1		: 1
	3		: 3
	2		: 2
	1		: 1
			; Consola
			: Datele de intrare sunt valide!
	==Explicație==		==Explicație==
	În intervalul [1,5] cmmdc-ul este 1		În intervalul [1,5] cmmdc-ul este 1
Line 97:		Line 99:
	print("Datele de intrare nu sunt valide!")		print("Datele de intrare nu sunt valide!")
	return		return
			else:
			print("Datele de intrare sunt valide!")
	st, logs = compute_sparse_table(a)		st, logs = compute_sparse_table(a)
	results = process_queries(a, queries, st, logs)		results = process_queries(a, queries, st, logs)

Cata: Pagină nouă: ==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, re...

2023-04-20T19:18:57Z

Pagină nouă: ==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, re...

New page

==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.

==Restricții și precizări==
* 1 &les; n &les; 100.000
* 1 &les; ai &les; 100.000
* 1 &les; q &les; 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
==Explicație==
Î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

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

if __name__ == '__main__':
main()

</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.

Funcția "main()" este funcția principală 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.

În final, condiția "if name == 'main':" verifică dacă codul este rulat ca script și apelează funcția principală.