5. Problematický tréning

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu variables_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

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

Zima sa blíži a Syseľ by sa pomaly chcel pobrať na zimný spánok¹. Ručička váhy sa však zastavila na vysokom čísle. Rozhodol sa teda, že bude trénovať, aby si pred tuhou zimou zlepšil kondičku. Rýchlo však zistil, že bezcieľne behanie po lese vôbec nie je efektívne. Nuž obrátil sa na Romana, profesionálneho bežca, ktorý mu ale tajomstvo svojho bežeckého umu nechcel prezradiť. Pri stretnutí s Romanom sa mu však podarilo zapamätať si časť jeho tréningového plánu.

Ten tvorí niekoľko po sebe idúcich čísel, ktoré symbolizujú zmeny v nadmorskej výške. Roman si pri behaní značí každú nezanedbateľnú zmenu v nadmorskej výške ako celé číslo. Kladným číslom ozačuje stúpania a záporným klesania. Pre názornú ukážku môže jeho plán vyzerať napríklad takto: [40, 20, -25, 5]. Vidíme, že ho na trase najskôr čakajú 2 stupáky (40 a 20), kedy dokopy stúpne o 60 výškových metrov, potom nasleduje jedno klesanie o 25 metrov a nakoniec malý kopček.

Syseľ má teraz v hlave nejakú časť Romanovho tréningového plánu, no stále nevie, aký úsek tohto plánu Roman za deň absolvuje. Uvedomil si ale jednu vec – Roman obľubuje bežať okruhy. Rád začína aj končí pri svojom dome, teda v rovnakej nadmorskej výške. Sysľovi preto stačí nájsť postupnosť, ktorej celková zmena v nadmorskej výške je nulová. V príklade vyššie by to bola časť [20, -25, 5].

Takýchto postupností môže samozrejme existovať viac. Ak ale nájde najdlhšiu takúto postupnosť, bude vedieť koľko najmenej musí zabehnúť, aby sa vyrovnal Romanovi. Čísel, ktoré si Syseľ zapamätal, je však veľa a preto vás požiadal o pomoc.

Úloha

Vašou úlohou je napísať program, ktorý na vstupe dostane postupnosť \(n\) čísel, reprezentujúcu časť Romanovho plánu, ktorú si Syseľ stihol zapamätať. Na výstup potom vypíše dĺžku, začiatok a koniec najdlhšej podpostupnosti, ktorej celková zmena nadmorskej výšky je nulová. V danej postupnosti teda hľadáte najdlhší úsek za sebou idúcich čísel, ktoré keď sčítate dokopy, dostanete výsledok 0.

Ak existuje takýchto najdlhších podpostupností viac, vypíšte ľubovoľnú z nich.

Formát vstupu

Na prvom riadku je číslo \(n\) – dĺžka postupnosti zapamätaných čísel. Na druhom riadku je \(n\) medzerou oddelených celých čísel. Každé z týchto čísel reprezentuje nárast alebo pokles nadmorskej výšky v poradí, v akom sa nachádzali v Romanovom pláne.

Formát výstupu

Na prvý riadok vypíšte dĺžku najdlhšej podpostupnosti so súčtom \(0\). Potom vypíšte na ďalší riadok ešte dve čísla oddelené medzerou – poradové číslo prvého a posledného čísla tejto podpostupnosti v pôvodnej postupnosti. Prvý prvok postupnosti má poradové číslo 0.

Ak takáto podpostupnosť neexistuje, vypíšte na jediný riadok výstupu hodnotu \(-1\).

Pri riešení v jazyku C++, Pascal, Java a podobných, si dávajte pozor na maximálne číslo, ktoré sú schopné celočíselné premenné uložiť. Súčet všetkých čísiel v postupnosti môže v poslednej sade tieto limity prekročiť. Odporúčame preto použiť \(64\)-bitové premenné, v jazyku C++ preto namiesto typu int použite typ long long int.

Riešení v Pythone sa takýto typ obmedzení netýka, pretože premenné v ňom majú neobmedzenú veľkosť.

Hodnotenie

Vaše riešenie bude otestované na \(3\) sadách vstupov. Za vyriešenie každej sady získate 5 bodov. Tieto sady sa líšia veľkosťou vstupných údajov. Nech \(n\) je dĺžka postupnosti a \(x\) je prvok tejto postupnosti, teda prevýšenie. Potom v jednotlivých sadách platí:

Príklady

Input:

10
5 2 17 3 -3 4 6 -5 -5 50

Output:

6
3 8

Ak si pozrieme podpostupnosť \([3, -3]\), vidíme, že táto podpostupnosť má nulový súčet. Nie je však najdlhšia možná. Najdlhšia takáto postupnosť je postupnosť \([3, -3, 4, 6, -5, -5]\), ktorá má dĺžku 6. Táto postupnosť začína na pozícii 3 (číslované od 0) a končí na pozícii 8.

Takýto vstup by sa mohol nachádzať v ľubovoľnej sade.

Input:

5
200 30 60 -2 12

Output:

-1

V tomto vstupe neexistuje podpostupnosť so súčtom 0.

Input:

3
7 8 0

Output:

1
2 2

Riešením môže byť aj podpostupnosť dĺžky 1.