4. Sekanie bambusu

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 Liahne (liahen.ksp.sk). Keď budeš riešiť sadu loops_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 Danovi na [email protected]

Globálne otepľovanie sa prejavuje stále viac a viac. Ľadovce sa topia. Hladiny oceánov sa dvíhajú. Živočíchy vymierajú. V ťažkej situácií je ale potrebné neprepadnúť panike a šíriť medzi ľuďmi radosť v podobe hudby. Na to však potrebujeme najdokonalejší hudobný nástroj. Tým je jednoznačne Panova flauta. Rozhodli ste sa, že nám ju vyrobíte z bambusu. My vás dovedieme ku bambusovému záhonu. V ňom sú bambusy rôznych výšok rastúce tesne vedľa seba v jednom dlhom rade. Sú medzi nimi také malé rozostupy, že nie je možné odseknúť bambus, ktorý je medzi dvoma inými bambusmi. V každom momente teda viete odseknúť iba bambus, ktorý je úplne vľavo, alebo úplne vpravo. Okamžite po odseknutí celý odseknutý bambus prilepíme na pravú stranu flauty.

Určite nechcete plytvať materiálom, preto bambus odseknete vždy celý a neostane z neho nad zem trčať ani kúsok. Zároveň však potrebujete bambusy sekať v takom poradí, aby bol každý ďalší odseknutý bambus dlhší, ako ten predchádzajúci. To je preto, že sa ponáhľame a nemáme dosť času na usporiadavanie toľkých paličiek ešte pred samotnou výrobou flauty. Bambusy musia byť vo flaute usporiadané podľa dĺžky, aby boli podobné tóny vedľa seba. No a nechceme predsa nejaký bambus odseknúť a zahodiť ho len preto, aby sme sa tým dostali k nejakému dlhšiemu. To je predsa zbytočný výrub lesov a proti tomu bojujeme.

Pozrime sa na príklad. Bambusy v záhone majú postupne zľava doprava výšky 1, 2, 5, 3, 2. Nám sa oplatí zobrať najskôr bambus naľavo s výškou 1. Máme teda flautu z jedného bambusu výšky 1. Ostane nám záhon s výškami 2, 5, 3, 2. Teraz zoberieme bambus úplne napravo s výškou 2. Flauta už je 1, 2 a záhon je ešte 2, 5, 3. Teraz zoberieme dvakrát bambus sprava a získame tak flautu 1, 2, 3, 5 a ostane nám záhon s jediným bambusom výšky 2. Postavili sme teda flautu šírky 4.

Čím viac tónov vieme zahrať, tým viac zachránime svet, to vie predsa každý. Chcete teda, aby flauta pozostávala z čo najviac bambusov. Akú najširšiu flautu nám viete postaviť?

Úloha

My vám popíšeme výšky bambusov tak, ako vedľa seba rastú v záhone. Vy chcete vyrobiť z bambusov flautu. To znamená, že sa v každom momente rozhodnete, či odseknete bambus vľavo, alebo bambus vpravo. Ten odseknete a pridáte ho ku flaute sprava. Odseknuté bambusy musia tvoriť rastúcu postupnosť.

Variant A

Zistite iba dĺžku najdlhšej rastúcej postupnosti, ktorú vieme vytvoriť vyššie popísaným spôsobom. Ináč povedané, vypíšte, koľko najviac bambusov vieme odseknúť tak, aby nám z toho vznikla flauta.

Variant B

Na získanie plného počtu bodov stačí vyriešiť Variant B

Nemusíte nám hovoriť dĺžku postupnosti. Vypíšte namiesto toho nejaký postup seknutí, ktorý nás dovedie k nejakej najdlhšej možnej flaute.

Formát vstupu

Na prvom riadku je číslo \(n\) - počet bambusov v záhone.

Na druhom riadku je \(n\) čísiel \(b_1\) až \(b_n\), výšky bambusov zľava doprava. Bude platiť, že \(1 \leq b_i \leq 2n\).

Formát výstupu

Variant A

Na jediný riadok výstupu vypíšte číslo \(k\) - najväčší možný počet bambusov vo flaute.

Variant B

Na jedinom riadku výstupu vypíšte reťazec dĺžky \(k\), kde \(k\) je najväčší možný počet bambusov vo flaute, ktorý sa dá dosiahnúť. Tento reťazec bude predstavovať postupnosť seknutí. Za každé odseknutie ľavého bambusu dajte znak L, za každé odseknutie bambusu sprava dajte znak R. Reťazec LRR teda bude znamenať, že sme najskôr odsekli ľavý potom pravý a potom znova pravý bambus.

Hodnotenie

Je 15 testovacích sád. Za každú viete získať 1 bod. Približne platí, že čím vyššie je číslo sady, tým väčšie je \(n\).

Ak riešite Variant A, vaše riešenia sa otestujú na všetkých sadách okrem 3, 6, 12, 15. Za toto riešenie teda viete získať až 11 bodov. Plný počet bodov dostanete, ak vyriešite Variant B. Takéto riešenie sa otestuje na všetkých sadách.

Interne testovanie vašich riešení funguje jednoduchým pravidlom. Ak je výstupom vášho programu číslo, testovač sa k nemu správa ako k riešeniu Variantu A. V opačnom prípade ho označí za riešenie Variantu B.

Navyše, sadách 1, 2, 3, 8, 9, 10, 11 a 12 sú všetky výšky bambusov rôzne. V ostatných sadách môžu byť niektoré výšky rovnaké.

Príklady

Variant B

Input:

5
1 2 5 3 2

Output:

LRRR

Vznikne flauta, kde dĺžky bambusov budú zľava doprava postupne 1, 2, 3, 5. Určite nemôžeme použiť všetky bambusy zo vstupu, pretože sú tam dva rovnakej dĺžky, takže by vzniknutá postupnosť určite nebola ostro rastúca.

Variant A

Input:

4
1 2 4 3

Output:

4

Môžeme použiť všetky bambusy zo vstupu