Fişierul intrare/ieşire:ab2.in, ab2.outSursăONI 2008, clasa a 9-a
AutorMircea Bogdan PasoiAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

Date de intrare

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

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.

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 ≤ i1 < i2 < ... < iM ≤ 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 ≤ 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.

Exemplu

ab2.inab2.out
4 2 3
1 4 3 2

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content