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

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()

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.