4. Súčty v električke

Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár - povie ti kde si spravil chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.

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

Kubo už odmalička sníva o tom, že bude jedného dňa šoférovať električku. Bohužiaľ zatiaľ ešte nemôže, a tak sa aspoň vozí z jednej zastávky na druhú, pozoruje ľudí, ktorí nastupujú a vystupujú, a robí si o tom všelijaké štatistiky.

Kubo si pre každú zastávku, cez ktorú prešiel, zapísal, koľko ľudí na nej dokopy nastúpilo alebo vystúpilo. Pre jednoduchosť predpokladajme, že na zastávke ľudia iba nastupujú alebo iba vystupujú - teda ak by napríklad nastúpilo \(10\) ľudí a vystúpilo \(7\), je to to isté ako keby iba nastúpili traja. Podobne ak by nastúpili dvaja a vystúpili štyria, je to akoby dokopy vystúpili dvaja. Kubo si píše počty nastupujúcich, takže keď ľudia vystupujú, zapíše si záporné číslo.

Úlohy

1. (20 bodov) Kuba často zaujíma otázka, koľko ľudí dokopy nastúpi na úseku od nejakej zastávky po nejakú ďalšiu. To môže spočítať tak, že sčíta počty nastupujúcich od tej prvej zastávky po tú druhú, ale ak sú tie zastávky ďaleko od seba, to je celkom veľa počítania a to sa mu nechce.

   Oveľa radšej by bol, keby vedel na každú takúto otázku nájsť odpoveď iba nejakým malým počtom sčítaní, bez ohľadu na to, ako ďaleko sú od seba zastávky. Aby to vedel urobiť, je ochotný napísať si nový zoznam, z ktorého to bude vedieť vyčítať lepšie ako z toho pôvodného.

   Navrhnite, čo si môže do toho nového zoznamu napísať, aby mu to pomohlo. Ako potom nájde odpovede na jeho otázky?

2. (10 bodov) Kubo už vie, ako hľadať odpovede na jeho otázky rýchlejšie, ale na to potrebuje ten svoj nový zoznam. Ako ho čo najefektívnejšie vypočíta z toho pôvodného?

3. (30 bodov) Niektoré úseky sú zvláštne tým, že na nich veľa ľudí nastupuje a málo vystupuje, alebo naopak. Chcel by nájsť taký úsek zastávok, kde sa toto deje najviac, teda na ktorom dokopy nastúpi najviac ľudí.

   Napríklad ak by počty nastupujúcich boli postupne \(3, -7, 5, -3, 6, -2\), potom najviac ľudí nastúpi na úseku od tretej po piatu zastávku, a to \(5 - 3 + 6 = 8\).

   Navrhnite, ako vie Kubo čo najefektívnejšie takýto úsek nájsť.

   Všimnite si, že keď Kubo nastupuje, v električke už môžu nejakí ľudia byť, a teda sa môže stať, že napríklad na druhej zastávke ich vystúpi viac ako ich na prvej nastúpilo.

4. (40 bodov) Na niektorých úsekoch naopak nastupuje veľmi málo cestujúcich. Niekedy sa dokonca stane, že na celom úseku dokopy akoby nenastúpil nikto - nejakí ľudia síce nastúpia, ale rovnaký počet aj vystúpi.

   Ak by počty nastupujúcich boli napríklad \(3, -5, 2, 3, -3\), potom takéto úseky sú štyri: od prvej po štvrtú zastávku, od druhej po piatu, od štvrtej po poslednú, a ešte aj od prvej po poslednú.

   Ako vie Kubo čo najefektívnejšie zistiť počet takýchto úsekov?