1899 - AfisMinime
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, 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
- 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
- Input valid
- 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("Input invalid")
sys.exit()
else:
print("Input valid")
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.