ultima problemă
grupă: micăsursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
tree
Timp maxim de executie/test:
0.1
secunde
Memorie totala disponibila/stiva:
16
MB/1 MB
Se considera o arborescenta
(arbore cu radacina) formata din N
noduri, numerotate de la 1 la
N . Nodul 1
este considerat radacina.
Cerinta
Scrieti un program care sa determine numarul
minim de arce care trebuie eliminate pentru a obtine un subarbore cu P
noduri. Subarborele obtinut nu trebuie sa contina neaparat nodul 1 .
Date
de intrare
Fisierul de intrare
tree.in contine pe prima linie
numerele naturale N si P ,
separate printr-un spatiu.N -1 linii contin
fiecare câte doua numere I
si J , cuprinse între 1
si N , separate printr-un spatiu,
cu semnificatia ca nodul J este
descendent direct al nodului I
(exista arc de la I la J ).
Date de iesire
In fisierul de iesire
tree.out va contine o singura
linie pe care se va scrie numarul natural X
reprezentand numarul de arce eliminate (minim posibil).
Restrictii
1 <=P <=
N <= 150
Exemplu
tree.in tree.out Explicatie
11 6
2
De exemplu, se elimina
arcele 1 5 si
1 4 .1 5 si 1
2 ).
prof. Dana
Lica danal182001@yahoo.com
Articole recomandate
Probleme recomandate
De la .campion 2005 : cuc , prime , radio , text2 , honest , police , comori , patrate3 , fisc , ref , pcod , zmeu , loc , nr01 , scor2 , judete , strict , convert , bile3 , cod2 , depou , auto2 , cat , nr3 , chimie2 , compress , jobs , leaves , zid , politics , onu2 , ploaia , grazing , pstring , cartonase2 , exp , cartoane , sir3 , program , scoici , playlist , sqr , cai1 , farfurii , joc1 , trafic , carte , set , barbie , labirint , firma1 , vile , game , donald , ambigram , dans , albinuta , rlcs , stea , submatrix , cub1 , ham , sponsori , young , jokes , pizza1 , albine , lot , atac1 , monede1 , count , exam , herbert , sudoku , bio , metro De acelaşi autor : compus , taste , arce , balbe , drept , scor , sume3 , spair , bitslang , police , reteta2 , farfurii , caramele , apm , maraton , masina1 , bomboane , soldati1 , concurs1 , puncte , pipe , camion , imax , litoral , dreptc , bal , prefix1 , tablite , lanturi , loto , bila , popic , activ , game1 , pitag , secv9 , divk , taler , bdotcom , oak , ozn1 , optim , puncte5 , swap , tetris3 , monede2 , ssk 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 , 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 , 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 arbori : bonuri , tgv , barfa , votare , arce , balaur , trains , bile2 , vmem , plopi , caravane , mese , strict , sub , kinder , firma1 , albinuta , rlcs , masina , omizi , concurs1 , latime , piloti , barca1 , arbnr , sirag1 , pikachu , arb , logn , maxq , arbore , bcast , mesaj1 , traseu , asmax , salvare , tramvai1 , omida , sediu , string , tv , izo , zoo , ratina , vitale , camion1 , arbfind , cezar1 , tcast , dep , curent , spp , frunze , sea2 , culori , color , urgenta , nori , treegame , antipatie , scanduri , minuni , arb1 , activ , regat , kdtree , autostrazi , carray , trenuri1 , arbgraf , war , mess , secvnumber , subs , posta , radare , arbore1 , hacker , lista , codarb , subsecvente , confuzie , transform , arbsum , copaci3 , arbvalmax