4. Statistics on the tram

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(a) chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.

Toto je pokračovanie úlohy z minulého kola. Ak si úlohu v minulom kole nevidel(a), môžeš si pozrieť jej zadanie aj vzorové riešenie, aj keď to na pochopenie tejto úlohy nie je nutné. Ak ste minulú úlohu riešili, môžete preskočiť rovno na časť čo je nové.

Ak máš hocijaké otázky k tejto úlohe, napíš Š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.

Z toho potom ráta, aký počet ľudí dokopy nastúpil na úseku medzi nejakými dvomi zastávkami. Už minule zistil, že aby to vedel robiť rýchlejšie, oplatí sa mu spočítať si prefixové súčty – teda namiesto počtov nastupujúcich si písať aktuálny počet ľudí v električke (presnejšie, o koľko viac ich tam je, než ich bolo, keď nastúpil, ak už v električke od začiatku boli nejakí ľudia).

Čo je nové

Lenže na poriadnu štatistiku treba veľa dát, nestačí sa pozrieť len na to, koľko ľudí nastupovalo v jeden konkrétny deň, treba to sledovať dlhodobo a potom sa pozrieť na priemer.

Kubo teda nazhromaždil dáta o počte nastupujúcich na nejakom úseku zastávok v priebehu niekoľkých dní (na každý deň jedna postupnosť). Teraz by chcel vedieť odpovedať na otázky, koľko priemerne ľudí dokopy nastúpi na nejakom úseku zastávok a v nejakom časovom úseku. No a aby vedel zrátať priemer, tak musí zrátať súčet a vydeliť to počtom dní.

Úlohy

Kubo má tabuľku, kde má počet nastupujúcich na každej zastávke každý deň.

1. (10 bodov) Kubo chce rýchlo odpovedať na otázky: koľko ľudí dokopy nastúpilo od prvej po \(k\)-tu zastávku za prvých \(d\) dní? Na to je ochotný spraviť si druhú tabuľku. Čo si do nej má napísať, aby potom už vedel rýchlo odpovedať?

2. (20 bodov) Ako vie takú tabuľku rýchlo vyrobiť (vypočítať, čo v nej má byť, z pôvodnej tabuľky)?

3. (30 bodov) Teraz by to chcel vedieť aj pre iný úsek zastávok alebo dní. Ako pomocou tej tabuľky rýchlo odpovie na otázky: koľko ľudí dokopy nastúpilo od \(a\)-tej po \(b\)-tu zastávku od \(c\)-teho po \(d\)-ty deň?

4. (40 bodov) Podobne ako minule, aj teraz Kuba zaujíma, na akom úseku nastúpilo dokopy najviac ľudí. Ako vie rýchlo nájsť taký úsek zastávok a dní, že v tých zastávkach a tých dňoch tam nastúpilo najviac ľudí?