1264 - StatisticiOrdine

Sursa: 1264 - Statistici Ordine

---

Cerinţa

Se dă un şir arr cu numar_elemente elemente, numere naturale. Să se afișeze al numar_dorit-lea cel mai mic element din șir.

Date de intrare

Programul citește din fișierul de intrare statisticiordine.in numărul numar_elemente și numar_dorit, iar apoi, pe rândul următor, cele numar_elemente elemente ale şirului arr.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse.", iar în fișierul de ieșire statisticiordine.out numărul căutat. În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, programul va afișa "Datele de intrare nu corespund restricțiilor impuse.", iar fișierul statisticiordine.out va ramane gol.

Restricţii şi precizări

• numar_elemente, numar_dorit ∈ ℕ
• 1 ⩽ numar_dorit ⩽ numar_elemente ⩽ 4.000.000
• element arr ∈ ℕ
• 0 ⩽ element arr < 4.000.000.000

Exemplu

Intrare statisticiordine.in

6 4

1 58 4 3 24 50

Ieșire Ecran

Datele de intrare corespund restricțiilor impuse.

Ieșire statisticiordine.out

24

Intrare statisticiordine.in

3 5

abc 63.5 -24

Ieșire Ecran

Datele de intrare nu corespund restricțiilor impuse.

Ieșire statisticiordine.out

Intrare statisticiordine.in

-2 3

Ieșire Ecran

Datele de intrare nu corespund restricțiilor impuse.

Ieșire statisticiordine.out

Rezolvare

Rezolvare ver. 1

# 1264 - Statistici Ordine

def validare_date_numar(numar_elemente: str, numar_dorit: str) -> bool:
    try:
        int(numar_elemente), int(numar_dorit)
        
        if 1 <= int(numar_elemente) <= 4_000_000 and int(numar_dorit) <= int(numar_elemente):
            return True
        else:
            raise ValueError
    except ValueError:
        return False
    
    
def validare_date_sir(lista: list) -> bool:
    return all(0 <= int(element) < 4_000_000_000 for element in lista)


def partition(arr: list, low: int, high: int):
    pivot = arr[high]
    
    indice1 = low - 1
    
    for indice2 in range(low, high):
        if arr[indice2] <= pivot:
            indice1 += 1
            arr[indice1], arr[indice2] = arr[indice2], arr[indice1]
    
    arr[indice1 + 1], arr[high] = arr[high], arr[indice1 + 1]
    
    return indice1 + 1


def quicksort(arr: list, low: int, high: int):
    if low < high:
        poz = partition(arr, low, high)
        quicksort(arr, low, poz - 1)
        quicksort(arr, poz + 1, high)
        

def statistici_ordine(arr: list, numar_elemente: int, pozitie: int) -> int:
    quicksort(arr, 0, numar_elemente - 1)
    
    return arr[pozitie - 1]


if __name__ == "__main__":
    file_input = open("statisticiordine.in", "r")
    file_output = open("statisticiordine.out", "w")
    
    line1 = file_input.readline()
    line1 = line1.split(" ")
    
    numar_elemente = line1[0]
    numar_dorit = line1[1]
    
    if validare_date_numar(numar_elemente, numar_dorit):
        numar_elemente, numar_dorit = int(numar_elemente), int(numar_dorit) 
        
        line2 = file_input.readline()
        arr = line2.split(" ")
        if validare_date_sir(arr):
            arr = list(map(int, arr))
            
            print("Datele de intrare corespund restricțiilor impuse.")
            file_output.write(str(statistici_ordine(arr, numar_elemente, numar_dorit)))
        else:
            print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")