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

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


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

Aurorei îi plac mult permutările. Ea defineşte o kmax-permutare ca fiind o permutare pentru care orice subsecvenţă a ei ce are elementele în ordine crescătoare, are lungime mai mică sau egală decât k. Acum, Aurora se întreabă câte kmax-permutări cu N elemente există.

Cerinţă

Pentru un N, k şi R daţi, aflaţi numărul de kmax-permutări cu N elemente. Rezultatul va fi calculat modulo R.

Date de intrare

Pe prima linie a fişierului de intrare kmax.in se vor afla numerele naturale N, k şi R, având semnificaţiile din enunţ, separate printr-un spaţiu.

Date de ieşire

Pe prima şi singura linie a fişierului de ieşire kmax.out veţi afişa numărul de kmax-permutări cu N elemente, modulo R.

Restricţii

1 ≤ k ≤ N ≤ 300
10 ≤ R ≤ 30000
• O subsecvenţă a unei permutări este formată din elemente situate pe poziţii consecutive.
• Pentru 20% din teste N ≤ 10
• Pentru 60% din teste N ≤ 150

Exemple

kmax.inkmax.outExplicaţii
4 2 997 17 Dintre cele 24 de permutări de 4 elemente următoarele 7 NU sunt 2max-permutări:
1 2 3 4
1 2 4 3
1 3 4 2
2 1 3 4
2 3 4 1
3 1 2 4
4 1 2 3
După câte observaţi toate cele 7 permutări de mai sus au cel puţin o secvenţă cu elementele în ordine crescătoare de lungime mai mare decât 2.
30 10 27017 21690

autor: Cosmin Gheorghe
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2010: diff, minuni, stalpi1, submatrix1, dreptunghiuri, gaz, xp, petrecere, triunghi2, cmmmc, simetric1, cern, pesti, plaja, tango, arb1, v2d, xor2, cuiburi, telefon, teroristi
De acelaşi autor: diff, kdtree, acerc, intervale
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, pizza1, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, expresii, arbnr, cod1, munte, shgraf, desc, lex, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, sg1, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, petrecere, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, module, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, matcnt, magic7, nmult, roua
surse trimise | ajutor