Zadanie

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.

Na začiatok si uvedomme čo po nás vlastne úloha žiada. Máme vytvoriť vežu z kusov bambusu, ktorá nespadne. Každý bambus má 1m a vie uniesť nad sebou \(n\)m bambusu. Čo to pre nás teda znamená? Máme rôzne čísla, ktoré chceme dať do nejakého poradia, aby za číslom \(k\) nasledovalo najviac \(k\) čísel a chceme aby bol tento rad čísel najdlhší možný zo zadanej množiny. Od teraz budeme hovoriť o takejto verzii úlohy.

Postupné stavanie radu

Predpokladajme, že už máme nejaký rad hotový a chceme k nemu nájsť ďalšie číslo. Očividne chceme použiť najväčšie dostupné číslo, aby sme vedeli aj naďalej rad rozširovať čo najviac. Použiť tam menšie číslo by znamenalo, že by sme zaň mohli pridať iba menej čísel. Aj keby sme toto väčšie číslo využili neskôr, nepomohli by sme si, lebo menšie číslo, ktoré sme využili skôr zaručene vynúti nižšiu maximálnu dĺžku radu ako by sme mohli dosiahnuť pomocou tohto väčšieho čísla.
V každom bode si pre aktuálny rad potrebujeme pamätať ešte jednu kľúčovú vlastnosť a tou je, aké máme aktuálne obmedzenie na jeho dĺžku. To si môžme pamätať ako počet prvkov, ktoré ešte môžme pridať (označíme ho \(l\)). Tento počet bude začínať na \(\infty\) a bude sa postupne meniť podľa toho, aké čísla pridávame. Ak pridáme číslo \(k\), tak \(l\) nového radu bude menšie číslo z \(l-1\) (predchádzajúce \(l\), mínus nové číslo) a \(k\) (za číslo \(k\) môže byť max. \(k\) čísel).
Ak sa dostaneme do situácie kde \(l=0\), tak vieme, že už nemôžme pridať žiadne ďalšie číslo a môžme sa zastaviť lebo už máme najdlhší rad.

Týmto sme opísali iteratívne riešenie, ktoré nám postupne postavý správny rad v čase \(O(n^2)\) (rad má najviac \(n\) prvkov a pre každý z nich musíme nájsť najvyššie nevyužité číslo, čo nám zaberie \(O(n)\) času). Toto ale vieme ľahko zrýchliť na \(O(n\log n)\), ak využijeme haldu.

Zjednodušenie

Čo si môžeme na vyššie popísanom riešení všimnúť je, že v podstate jediné čo robíme je, že vždy berieme najväčšie ešte nevyužité číslo. To vieme veľmi ľahko urobiť, ak si rad hneď na začiatku zoradíme zostupne. Potom už stačí len brať prvky z jeho začiatku a máme zaistené, že vždy berieme najväčšie doteraz nevyužité číslo. Samozrejme, nesmieme zabudnúť na obmedzenie \(l\), ale to už vieme ľahko skontrolovať pri lineárnom prechádzaní radu.

Takéto riešenie už má časovú zložitosť \(O(n\log n)\), nakoľko zoradenie radu nám zaberie \(O(n\log n)\) času a potom už len lineárne prechádzame rad a kontrolujeme obmedzenie \(l\).

Implementácia

Najzložitejšia časť riešenia je vypísanie radu, nakoľko nevypisujeme prvky, ale ich index z pôvodného radu. To vieme ľahko urobiť, ak si na začiatku prvky zapamätáme ako dvojicu čísel namiesto jedného. Prvým číslom bude samotný prvok a druhým jeho index. Potom môžeme vo väčšine jazykov použiť zabudovanú funkciu na zoradenie. Dvojice zoradí primárne podľa prvého prvku (t.j. to čo chceme) a až v prípade jeho rovnosti podľa druhého prvku (to nás už netrápi). V Pythone sa na dvojice dá využiť tuple a zabudovaná funkcia sort, v C++ by to bol pair a sort.

V Pythone by sme mohli riešenie napísať nasledovne:

n = int(input())
# kadzy prvok si naformatujeme ako (prvok, index)
k = [(int(x), i) for i, x in enumerate(input().split())]

# zoradime prvky zostupne
k.sort(reverse=True)

# pouzijeme -1 ako nekonecno
l = -1
i = 0
while i < n:
	if l == 0:
		# uz nemozme pridat ziadne dalsie cislo
		break
	if i == 0:
		# pridame prvy prvok, l musi byt k
		l = k[i][0]
	else:
		# pridame dalsi prvok, l je minimum z l-1 a k
		l = min(l-1, k[i][0])
	i += 1

# vypiseme pocet prvkov, ktore ma rad
print(i)
for j in range(i):
	# vypiseme indexy prvkov
	print(k[j][1], end='')
	if j < i-1:
		print(' ', end='')
print()

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.