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

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


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

Un gospodar are N iepuri (pe care i-a numerotat de la 1 la N) şi foarte mulţi morcovi. Ce e mai deosebit în această gospodărie este că iepurii sunt organizaţi ierarhic, în funcţie de vârstă, autoritate şi nevoile nutriţionale. Astfel, fiecare iepure are exact un şef direct (exceptându-l pe Rilă Iepurilă, care este şeful cel mare, şeful tuturor iepurilor). Orice iepure poate avea 0, 1 sau mai mulţi subordonaţi direcţi. Orice iepure-şef va mânca cel puţin un morcov mai puţin decât fiecare dintre subordonaţii săi direcţi.
Gospodarul nu se poate hotărî câţi morcovi să dea fiecărui iepure şi ar vrea să ştie în câte moduri poate împărţi morcovi la iepuri ştiind că fiecare iepure poate să mănânce minim un morcov şi maxim K morcovi.

Cerinţă

Scrieţi un program care calculează numărul de posibilităţi modulo 30011 de a împărţi morcovi la cei N iepuri ştiind că orice iepure poate mânca între 1 şi K morcovi şi trebuie să mănânce cu cel puţin un morcov mai puţin decât fiecare dintre iepurii care îi sunt subordonaţi direcţi.

Date de intrare

Fişierul de intrare iepuri.in conţine:
- pe prima linie două numere naturale N şi K, separate printr-un spaţiu, reprezentând numărul de iepuri, respectiv numărul maxim de morcovi ce pot fi mâncaţi de un iepure.
- pe fiecare din următoarele N-1 linii se află câte două numere naturale distincte a şi b, cuprinse între 1 şi N, separate printr-un spaţiu, cu semnificaţia că iepurele a este şeful direct al iepurelui b.

Date de ieşire

Fişierul de ieşire iepuri.out va conţine numărul de moduri de a împărţi morcovii conform condiţiilor specificate în enunţ, modulo 30011.

Restricţii

1<= N, K <= 100
Numărul ce trebuie scris în fişierul de ieşire va fi afişat modulo 30011.

Exemple

iepuri.iniepuri.out
9 4 7 2 7 3 7 4 3 5 3 6 5 8 5 9 6 1 9

autor: Iolanda Popa
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la OJI 2008: pluricex, concurs, piata, numar, turist
De acelaşi autor: strict, rlcs, herbert, masina
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, 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, 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
surse trimise | ajutor