Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kubovi na [email protected]
Jedného krásneho dňa sa Kodik vybral na tajomnú cestu Čínou. Cestoval už dlho a ďaleko, mal so sebou aj nejaké to jedlo, však poriadna panda musí pravidelne papkať. Cesta je však dlhšia ako očakával a už mu nezostáva veľa jedla. Našťastie je neďaleko bambusového hája, kde sa môže napapať. Tá horšia vec je, že odtiaľ musí pokračovať ďalej a nevie, či nájde po ceste ešte nejaké jedlo. Preto sa rozhodol, že si z bambusového hája vezme čo najviac bambusu. Nemá však veľké rozpätie rúk a preto by si chcel z kusok bambusu urobiť jednu, čo najvyššiu vežu. To ale nebude až tak jednoduché, keďže každý kus bambusu má iný tvar a teda aj inú nosnosť. Viete mu s tvorením takejto veže pomôcť?
Máme $n$ kusov bambusu. Každý kus má výšku $1m$ a silu $a_i$. Každý kus bambusu vie
uniesť $a_i$ metrov bambusu nad sebou. Ak by mal nad sebou viac ako $a_i$ metrov bambusu,
zlomil by sa. Kodik chce z týchto kusov bambusu vytvoriť čo najvyššiu vežu tak, že ich
bude skladať na seba. Zároveň chceme, aby sa žiaden kus bambusu nezlomil.
Akú najvyššiu vežu vieme z týchto kusov bambusu postaviť?
Na prvom riadku je celé číslo $n$ ($1 \leq n \leq 750000$) udávajúce počet kusov bambusu.
Na ďalšom riadku sa nachádza $n$ celých čísel $a_i$ ($0 \leq a_i \leq 10^{8}$), z ktorých
$i$-te číslo udáva silu $i$-teho kusu bambusu.
Na prvý riadok výstupu vypíšte jedno celé číslo - najvyššiu vežu, ktorú vieme z týchto kusov
bambusu postaviť.
Na nasledujúcom riadku vypíšte rad čísel $i_1, i_2, \dots, i_k$ oddelených medzerami,
označujúce indexy kusov bambusu (z pôvodného poradia), ktoré sú súčasťou najvyššej veže
od spodu po vrch.
Ak je riešení viacero, vypíšte ľubovoľné z nich.
Existujú 4 sady vstupov, za každú z nich môžete získať 25 bodov. Platia v nich nasledovné obmedzenia:
| Sada | 1. | 2. | 3. | 4. |
|---|---|---|---|---|
| $1 \leq n \leq$ | $100$ | $15000$ | $200000$ | $300000$ |
| $0 \leq a_i \leq$ | $100$ | $10000$ | $10^7$ | $10^8$ |
5
3 2 0 2 3
4
0 4 1 3
Ďalšie správne riešenie by mohlo byť napríklad 4 0 1 3.
3
1 2 0
3
1 0 2
Iné riešenie neexistuje.