Zoznam úloh

1. Prefixová expedícia

Kolo už skončilo. Môžeš si pozrieť vzorové riešenie.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Romanovi na [email protected]

Macín a Ondro sú ostrieľaní lezci a na jar sa rozhodli vyraziť za adrenalínom do Tatier. Pred expedíciou si kúpili turistickú mapu, ktorá vyzerala nasledovne:

![](obrazky/mapa.png)

Medzi každými dvoma vrcholmi na mape je jedno číslo, ktoré reprezentuje rozdiel nadmorskej výšky pravého a ľavého vrcholu. Macín s Ondrom sa po mape budú pohybovať zľava doprava. Nevedia však, v ktorom vrchole svoju expedíciu začnú a preto potrebujú pomoc pri výbere trasy.

Úloha

Vrcholy z mapy si očíslujeme zľava doprava $0$ až $N$. Údaje o nadmorských výškach budeme reprezentovať pomocou poľa $A$, ktoré obsahuje jednotlivé rozdiely. Prvok $A[i]$ obsahuje rozdiel medzi výškou vrchola $i+1$ a $i$. Pole $A$ pre našu mapu vyzerá nasledovne:

![](obrazky/a_arr.png)

Terka chalanom poradila, aby si predpočítali pre pole $A$ prefixové súčty. Ide o list, na ktorého $i$-tej pozícii je súčet všetkých čísel, ktoré sú v pôvodnej postupnosti na pozíciách od $0$ po $i - 1$. Pre pole $A$ bude preto pole $P$ prefixových súčtov vyzerať nasledovne:

![](obrazky/p_arr.png)

Všimnite si, že tento list je o jedna dlhší ako $A$ a začína $0$. Na $0$-tej pozícii totiž musí byť súčet čísel od $0$ po $−1$, čo je $0$. Napríklad na $3$-tej pozícii je $6$, pretože súčet prvých $3$ čísel poľa $A$ je $3 - 1 + 4 = 6$.

  1. (2 body) Ondru pred cestou zaujíma, kde má mapa svoje stredové vrcholy. Stredový vrchol je taký vrchol, pre ktorý je súčet rozdielov z najľavejšieho vrcholu na mape rovnaký ako súčet rozdielov od najpravejšieho vrcholu na mape. Presnejšie teda hľadáme všetky vrcholy $k$ také, že $$A[0] + \dots + A[k - 1] = A[k] + \dots + A[N - 1]$$ Napríklad na mape zo začiatku zadania sú stredovými vrcholmi vrcholy $3$ a $6$. Vymyslite ako efektívne nájsť stredové vrcholy pre pole $A$. Efektívnym riešením v tomto prípade myslíme také, ktoré pristupuje k jednotlivým prvkov poľa $A$ a $P$ čo najmenejkrát. Pošlite nám slovný popis vášho postupu. Váš popis by mal byť zrozumiteľný aj bez znalosti programovania a mal by ho vedieť odsimulovať ktokoľvek s perom a papierom.

  2. (2 body) Macín a Ondro plánujú špeciálnu túru, pri ktorej skončia v rovnakej nadmorskej výške, z akej vyrážali. To znamená, že celkový súčet rozdielov nadmorských výšok na trase je rovný $0$. Viete im poradiť, ako pomocou prefixových súčtov nájsť súvislý úsek v poli $A$, ktorého súčet je $0$? Pri tejto podúlohe neposielajte algoritmus, iba popíšte, ako si v poli prefixových súčtov všimnúť úsek so súčtom $0$.

  3. (3 body) Chalanov pri plánovaní často zaujíma, aký je celkový rozdiel nadmorskej výšky medzi konkrétnymi dvoma vrcholmi. Napríklad pre vrcholy $2$ a $5$ je celkový rozdiel $4 - 3 + 5 = 6$. Všimnite si, že pre vrcholy $a$ a $b$ také, že $a < b$, vieme vypočítať celkový rozdiel ako súčet čiastkových rozdielov, tj. $A[a] + A[a + 1] + … + A[b - 1]$. Macín ale stále prichádza s novými nápadmi na trasy a Ondrovi sa už nechce počítať rozdiely prvok po prvku. Musí to ísť predsa lepšie! Vašou úlohou je preto prísť na to, ako šikovne spočítať celkový rozdiel medzi výškami vrcholov $a$ a $b$ pomocou poľa prefixových súčtov $P$.

  4. (3 body) Ako pre pole $A$ vytvoriť pole prefixových súčtov $P$? Podobne ako v podúlohe a) vymyslite efektívne riešenie, teda také, ktoré k prvkom poľa $A$ a $P$ prístupi čo najmenejkrát, a pošlite nám jeho slovný popis.

  5. (5 bodov) Telo sa musí vyššej nadmorskej výške vždy prispôsobiť. Výstupiť preto za jeden deň oveľa vyššie a prenocovať tam by mohlo byť nebezpečné. Chalani si určili výšku $k$, o ktorú chcú za jeden deň vystúpiť vyššie. Vašou úlohou bude nájsť všetky dvojice vrcholov, medzi ktorými je celkový rozdiel nadmorských výšok práve $k$. Napríklad na našej mape by pre $k = 4$ splňovali túto podmienku dvojice vrcholov $(2, 3)$ a $(2, 6)$. Opäť nám pošlite slovný popis čo najefektívnejšieho riešenia.

Ak viete programovať, niektoré z podúloh si môžete vyskúšať naprogramovať a poslať nám vaše kódy. Nedostanete síce body naviac, ale vaše programy okomentujeme a poradíme vám, čo by sa dalo spraviť lepšie alebo krajšie. Pri programátorských úlohách vám nedávame spätnú väzbu k vašim programom, preto máte teraz jedinečnú šancu.

P.S.: Ondro s Macínom a kamarátmi Tatry skutočne navštívili. Ako sa Čechom v Tatrách darilo a či ich zachraňovala horská služba, sa dozviete v článku od Ondru.

Pre odovzdávanie sa musíš prihlásiť.