Zoznam úloh

4. Strašne veľa uhoriek

Zadanie

Odkedy Lukáš aspoň trochu tuší, ako fungujú ženy, ich vzťah je výrazne šťastnejší. Dokonca si spolu kúpili dom s veľkou záhradou a ako prvú vec zasadili uhorky. Neskôr však prišli čoraz častejšie hádky, najmä kvôli neskutočnému objemu uhoriek, ktoré Julka núti Lukáša zjesť. Tá pred neho poukladala rad z uhoriek. Lukáša by zaujímalo, koľko je uhoriek na rôznych úsekoch radu.

Úloha

Lukášov rad uhoriek si vieme predstaviť ako zoznam $l$ čísel, ktoré reprezentujú veľkosti uhoriek. Vašou úlohou bude odpovedať na $n$ otázok, ktoré sa pýtajú na súčet veľkostí uhoriek od $a$ po $b$.

Formát vstupu

V prvom riadku je jedno číslo,$l$ Ďalej nasleduje $l$ čísel oddelených medzerou, čo predstavujú uhorky pred Lukášom. Na treťom riadku je $n$, po ktorom nasleduje $n$ riadkov vo formáte $a$ $b$, reprezentujúci otázku na súčet od $a$ po $b$.

Formát výstupu

Ako odpoveď vypíš $n$ riadkov, postupne odpovedajúcich na položené otázky jedným číslom.

Príklad

Vstup

10
2 5 3 4 2 4 1 3 5 9
2
0 7
3 5

Výstup

24
10

Súčet čísel od 0 po 7 je 24, zatiaľ čo súčet od 3 do 5 je 4+2+4=10

Táto úloha sa riešila pomocou prefixových súm. O nich sa viac dočítaš tu.

Ak by musel Lukáš pri každej otázke rátať súčet všetkých uhoriek, trvalo by mu to príliš dlho. Táto časová zložitosť by bola $O(ld)$, keďže každá otázka môže potenciálne robiť až $l$ operácií.

Preto si Lukáš predpočíta prefixovú sumu, čo mu trvá $O(l)$. Následne na každú otázku vie odpovedať v $O(1)$ keďže to je iba odčítanie dvoch čísel. Keďže otázok je $d$, tak celková komplexita bude $O(l+d)$. Takýto program by vyzeral nasledovne:

otazky = []
prefixova_suma = [0]
n = int(input())
velkosti_uhoriek = list(map(int,input().split()))
m = int(input())

for i in range(m): # Načítanie otázok
    otazky.append(list(map(int,input().split())))


for i in range(n): # Zrátame prefixové sumy
    prefixova_suma.append(prefixova_suma[i] + velkosti_uhoriek[i])


for i in range(m): # Odpovedáme na otázky
    odpoved = prefixova_suma[otazky[i][1]+1] - prefixova_suma[otazky[i][0]]
    print(odpoved)
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Súťaž PRASK zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty