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ť?
Úloha
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ť?
Formát vstupu
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.
Formát výstupu
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.
Hodnotenie a obmedzenia
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\) |
Príklady
Input:
5
3 2 0 2 3
Output:
4
0 4 1 3
Ďalšie správne riešenie by mohlo byť napríklad 4 0 1 3
.
Input:
3
1 2 0
Output:
3
1 0 2
Iné riešenie neexistuje.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.