ultima problemă
grupă: micăsursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
kdist
Timp maxim de execuţie/test:
0.1
secunde
Memorie totala disponibilă/stivă:
16MB/1 MB
Se dă un şir de N numere naturale din intervalul [1, N] şi un număr natural K .
Cerinţă
Să se determine câte subşiruri cu cel mult K elemente distincte există în şirul dat.
Date de intrare
Fişierul de intrare kdist.in va conţine pe prima linie numere naturale N şi K separate printr-un spaţiu. Pe a doua linie se află N numere naturale separate prin spaţii, reprezentând elementele şirului.
Date de ieşire
Fişierul de ieşire kdist.out va conţine o singură linie pe care se află numărul de subşiruri ale şirului dat care au cel mult K elemente distincte. Rezultatul va fi afişat modulo 30007 .
Restricţii
1 ≤ N ≤ 1000 1 ≤ K ≤ N Pentru 20% din teste N ≤ 15
Un subşir conţine cel puţin un element.
Exemplu
kdist.in kdist.out Explicaţie
4 2 12 Cele 12 subşiruri cu cel mult 2 elemente distincte sunt:1
Articole recomandate
Probleme recomandate
De la .campion 2010 : greiere , divizori , pestera , partitie , sokoban , pitag , porumb , cheie , conferinta , chei , stelar , atelier , secv9 , ny , radical , arbgraf , select , divk , bileprime , nx , reuniune , cazare , proiect , taler , atletism , echipa , ghinion , oldest , war , aliniere , sumb , cavaleri , joct , fluviu , camera616 , aritm , stele , covor , subm , mess , secvnumber , cladire , ssmax , parcela , pion , subs , universitate , el , mahjong , rotund , sirmax , bdotcom , pack De acelaşi autor : votare , nkbiti , kperms , site , kbiti , oldest , mess , subs , subsiruri 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 , kmax , stalpi1 , gaz , triunghi2 , v2d , cuiburi , mine , orientare , activ , secvbiti , kcons , pokemon , ubergraf , left , acerc , autostrazi , 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 , kmax , petrecere , tango , rege , cd1 , cifru3 , kcons , bubblesort , hawaii , randomizare , 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