Diferente pentru problema/ab2 intre reviziile #2 si #7

Diferente intre titluri:

ab2
Ab2

Diferente intre continut:

== include(page="template/taskheader" task_id="ab2") ==
Poveste si cerinta...
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$.
h2. Date de intrare
Fisierul de intrare $ab2.in$ ...
Fisierul de intrare $ab2.in$ va contine pe prima linie numerele $N$, $A$ si $B$.
h2. Date de iesire
In fisierul de iesire $ab2.out$ ...
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.
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 |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 4 2 3
| 1 4 3 2
|
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") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3090