.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » ab2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
ab2


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

Una din cele mai noi pasiuni ale lui Zăhărel este să studieze diverse proprietăţi ale permutărilor. De exemplu, este interesat de permutările în care cel mai lung subşir crescător şi cel mai lung subşir descrescător au lungimi date.

Cerinţă

Să se scrie un program care determină o permutare de lungime N în care cel mai lung subşir crescător are lungime A şi cel mai lung subşir descrescător are lungime B.

Date de intrare

Fişierul de intrare ab2.in va conţine pe prima linie numerele N A B.

Date de ieşire

Fişierul de ieşire ab2.out va conţine pe prima linie N numere separate prin câte un spaţiu, reprezentând o permutare care respectă condiţiile de mai sus. Dacă există mai multe soluţii, se va afişa cea minimă din punct de vedere lexicografic.

Restricţii

1 ≤ N,A,B ≤ 30.000
Se garantează că mereu există soluţie pentru datele de intrare
Se numeşte subşir al şirului X=(x1,x2...xN), un şir Y=(xi1,xi2...xiM) cu proprietatea
1≤i1<i2<...<iM≤N
Un şir (x1,x2...xK) este mai mic din punct de vedere lexicografic decat un alt şir (y1,y2...yK) dacă există o poziţie p≤K, astfel încat xp<yp si x1=y1, x2=y2 ... xp-1=yp-1
Pentru un test se va acorda 70% din punctaj dacă permutarea afişată are cel mai lung subşir crescător de lungime A şi cel mai lung subşir descrescător de lungime B, dar nu este minimă lexicografic.

Exemple

ab2.inab2.outExplicaţii
4 2 3 1 4 3 2 Cel mai lung subşir crescător are lungime 2 (1 4, 1 3 sau 1 2), iar cel mai lung subşir descrescător are lungime 3 (4 3 2).
O altă soluţie posibilă este 2 4 3 1, dar aceasta nu este minimă din punct de vedere lexicografic.

autor: Mircea Paşoi
propunător: Stud. Vlad Manea
Facultatea de Informatică
vlad.c.manea@gmail.com
Probleme recomandate
De la ONI 2008: iepuras, palind, auto, div, teatru, pm, submat, reteta2, rezervatie, creioane, melci, mere2, felinare, joc3, 2numere, fi, tablou, borcane, mexc, tcast, dep, dist1, stiva, banda, pavare, poarta, aranjare, bile4, subgeom, albinuta1, curent, pviz, atac2, virus
De acelaşi autor: copaci, plimbare, cuvinte, pioni, reinvent, numere3, perm, criptare, sume, gramezi, nr2, rev, paintball, matricea, emax, turism, puncte1, casute, dep
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor