Ab2

ab2

== include(page="template/taskheader" task_id="ab2") ==

Una din cele mai noi pasiuni ale lui Zaharel este sa studieze diverse proprietati ale permutarilor. De exemplu, este interesat de permutarile in care cel mai lung subsir crescator si cel mai lung subsir descrescator au lungimi date.
 
h2. Cerinta
 
Sa se scrie un program care determina o permutare de lungime $N$ in care cel mai lung subsir crescator are lungime $A$ si cel mai lung subsir descrescator are lungime $B$.

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $ab2.in$ va contine pe prima linie numerele $N$, $A$ si $B$.

Fisierul de intrare $ab2.in$ ...

h2. Date de iesire

Fisierul de iesire $ab.out$ va contine pe prima linie $N$ numere separate prin cate un spatiu, reprezentand o permutare care respecta conditiile de mai sus. Daca exista mai multe solutii, se va afisa cea minima din punct de vedere lexicografic.

In fisierul de iesire $ab2.out$ ...

h2. Restrictii

* $1 ≤ N, A, B ≤ 30 000$
* Se garanteaza ca mereu exista solutie pentru datele de intrare.
* Se numeste subsir al sirului $X = (x ~1~, x ~2~...x ~N~)$, un sir $Y = (x ~i1~, x ~i2~... x ~iM~)$ cu proprietatea $1 &le; i1 < i2 < ... < iM &le; N$.
* Un sir $(x ~1~, x ~2~ ... x ~K~)$ este mai mic din punct de vedere lexicografic decat un alt sir $(y ~1~, y ~2~ ... y ~K~)$ daca exista o pozitie $p &le; K$, astfel incat $x ~p~ < y ~p~$ si $x ~1~ = y ~1~, x ~2~ = y ~2~ ... x ~p-1~ = y ~p-1~$.
* Pentru un test se va acorda 70% din punctaj daca permutarea afisata are cel mai lung subsir crescator de lungime $A$ si cel mai lung subsir descrescator de lungime $B$, dar nu este minima lexicografic.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. ab2.in |_. ab2.out |

| 4 2 3
| 1 4 3 2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

Cel mai lung subsir crescator are lungime 2 (1 4, 1 3 sau 1 2), iar cel mai lung subsir descrescator are lungime 3 (4 3 2).
O alta solutie posibila este 2 4 3 1, dar aceasta nu este minima din punct de vedere lexicografic.
 

...

== include(page="template/taskfooter" task_id="ab2") ==