Cata at 06:16, 3 May 2023

2023-05-03T06:16:24Z

← Older revision		Revision as of 06:16, 3 May 2023
Line 8:		Line 8:

	==Date de ieșire==		==Date de ieșire==
	În fișierul de ieșire afisminime.out, se va afișa un mesaj de validare a datelor, după care vor fi m linii, fiecare conținând câte un număr, pe linia i aflându-se răspunsul pentru întrebarea i.		În fișierul de ieșire afisminime.out, se va afișa un mesaj de validare a datelor, după care vor fi m linii, fiecare conținând câte un număr, pe linia i aflându-se răspunsul pentru întrebarea i. Consola rămâne goală.

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

Cata at 07:19, 28 April 2023

2023-04-28T07:19:34Z

← Older revision		Revision as of 07:19, 28 April 2023
Line 8:		Line 8:

	==Date de ieșire==		==Date de ieșire==
	În fișierul de ieșire afisminime.out, vor fi m linii, fiecare conținând câte un număr, pe linia i aflându-se răspunsul pentru întrebarea i.		În fișierul de ieșire afisminime.out, se va afișa un mesaj de validare a datelor, după care vor fi m linii, fiecare conținând câte un număr, pe linia i aflându-se răspunsul pentru întrebarea i.

	==Restricții și precizări==		==Restricții și precizări==
Line 15:		Line 15:
	* 1 ≤ x , y ≤ n		* 1 ≤ x , y ≤ n
	==Exemplu==		==Exemplu==
	afisminime.in		; afisminime.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		; afisminime.out
	afisminime.out		: Input valid
			: 1
	1		: 3
	3		: 2
	2		: 2
	2
	==Explicație==		==Explicație==
	în intervalul [1 , 5] minimul este 1		în intervalul [1 , 5] minimul este 1
Line 85:		Line 84:

	if not validate(n, q, arr):		if not validate(n, q, arr):
	print("~~Invalid input~~")		print("Input invalid")
	sys.exit()		sys.exit()
			else:
			print("Input valid")

	res = solve(n, q, arr)		res = solve(n, q, arr)

Cata: Pagină nouă: ==Cerința== Se dă un vector cu n elemente, numere naturale. Fie două numere x și y, cu proprietatea că 1 ≤ x , y ≤ n. Scrieți un program care răspunde la m întrebări de tipul “Care este elementul minim din intervalul [x , y]?”. ==Date de intrare== Pe prima linie a fișierului afisminime.in sunt date numerele n și m. Pe a doua linie se vor afla n numere naturale, fiind elementele vectorului. Următoarele m linii vor conține câte 2 numere reprezentând val...

2023-04-20T12:33:35Z

Pagină nouă: ==Cerința== Se dă un vector cu n elemente, numere naturale. Fie două numere x și y, cu proprietatea că 1 ≤ x , y ≤ n. Scrieți un program care răspunde la m întrebări de tipul “Care este elementul minim din intervalul [x , y]?”. ==Date de intrare== Pe prima linie a fișierului afisminime.in sunt date numerele n și m. Pe a doua linie se vor afla n numere naturale, fiind elementele vectorului. Următoarele m linii vor conține câte 2 numere reprezentând val...

New page

==Cerința==
Se dă un vector cu n elemente, numere naturale. Fie două numere x și y, cu proprietatea că 1 ≤ x , y ≤ n.

Scrieți un program care răspunde la m întrebări de tipul “Care este elementul minim din intervalul [x , y]?”.

==Date de intrare==
Pe prima linie a fișierului afisminime.in sunt date numerele n și m. Pe a doua linie se vor afla n numere naturale, fiind elementele vectorului. Următoarele m linii vor conține câte 2 numere reprezentând valorile x și y, care definesc întrebările.

==Date de ieșire==
În fișierul de ieșire afisminime.out, vor fi m linii, fiecare conținând câte un număr, pe linia i aflându-se răspunsul pentru întrebarea i.

==Restricții și precizări==
* 1 ≤ n ≤ 100.000
* 1 ≤ m ≤ 1.000.000
* 1 ≤ x , y ≤ n
==Exemplu==
afisminime.in

5 4
1 3 18 2 3
1 5
2 3
3 4
2 4
afisminime.out

1
3
2
2
==Explicație==
în intervalul [1 , 5] minimul este 1
în intervalul [2 , 3] minimul este 3
în intervalul [3 , 4] minimul este 2
în intervalul [2 , 4] minimul este 2

==Rezolvare==
<syntaxhighlight lang="python">
import sys
from typing import List

def query(i: int, j: int, r: List[List[int]], lg2: List[int]) -> int:
e = lg2[j - i + 1]
p2 = 1 << e
return min(r[e][i + p2 - 1], r[e][j])

def solve(n: int, q: int, arr: List[int]) -> List[int]:
NMAX = 10 ** 5
r = [[0] * (NMAX + 1) for _ in range(17)]
lg2 = [-1] * (NMAX + 1)
res = []

for i in range(1, n + 1):
x = arr[i-1]
r[0][i] = x
lg2[i] = 1 + lg2[i >> 1]

for i in range(1, lg2[n] + 1):
for j in range(1 << i, n + 1):
r[i][j] = min(r[i - 1][j - (1 << (i - 1))], r[i - 1][j])

for i in range(q):
x, y = map(int, input().split())
res.append(query(x, y, r, lg2))

return res

def validate(n: int, q: int, arr: List[int]) -> bool:
if not (1 <= n <= 100000):
return False
if not (1 <= q <= 1000000):
return False
for i in arr:
if not (1 <= i <= n):
return False
return True

if __name__ == "__main__":
# Input and output files
sys.stdin = open('afisminime.in', 'r')
sys.stdout = open('afisminime.out', 'w')

n, q = map(int, input().split())
arr = [int(input()) for i in range(n)]

if not validate(n, q, arr):
print("Invalid input")
sys.exit()

res = solve(n, q, arr)
for r in res:
print(r)

sys.stdin.close()
sys.stdout.close()

</syntaxhighlight>

==Explicatie cod==
Acest cod Python definește trei funcții și un validator de intrare pentru a rezolva o problemă specifică de programare.

Funcția "query" primește ca parametri o pereche de numere întregi și două liste de întregi. Scopul acestei funcții este de a returna valoarea minimă din intervalul inclus între cele două numere întregi în prima listă, utilizând informațiile stocate în a doua listă.

Funcția "solve" primește ca parametri un număr întreg n, un număr întreg q și o listă de întregi. Scopul acestei funcții este de a rezolva problema specifică de programare, unde trebuie să găsești valoarea minimă dintr-un interval de elemente din lista dată. Aceasta construiește o matrice pentru a memora informațiile necesare, apoi calculează valorile minime pentru fiecare interval de dimensiuni diferite, folosind funcția "query", și le stochează într-o listă numită "res".

Funcția "validate" primește ca parametri același tip de date ca funcția "solve". Scopul acestei funcții este de a verifica dacă input-ul dat este valid pentru problema specifică de programare. Aceasta verifică dacă dimensiunile listei de intrare și a intervalului sunt în limitele permise și dacă toate elementele din lista de intrare sunt cuprinse în intervalul de la 1 la n.

În blocul "if name == "main":", codul deschide fișierele de intrare și ieșire, citeste input-ul, verifică dacă input-ul este valid și apelează funcția "solve" dacă input-ul este valid. În cele din urmă, funcția "solve" afișează output-ul în fișierul de ieșire și închide fișierele de intrare și ieșire.

1899 - AfisMinime - Revision history

Cata at 06:16, 3 May 2023

Cata at 07:19, 28 April 2023