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.