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

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


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

Mitruţ are primele N numere naturale nenule şi un arbore cu rădăcină cu N noduri. El se întreabă în câte feluri poate plasa cele N numere în nodurile arborelui, astfel încât fiecare nod să conţină un număr mai mic decât toate numerele din fiii săi.

Cerinţă

Scrieţi un program care să răspundă la întrebarea lui Mitruţ prin afişarea numărului de modalităţi distincte de plasare a numerelor în arbore conform metodei de mai sus, modulo 666013.

Date de intrare

Fişierul arbore1.in conţine pe prima linie numărul N cu semnificaţia din enunţ. Următoarele N–1 linii vor conţine fiecare câte două numere întregi x y, cu semnificaţia că există muchie între nodurile x şi y.

Date de ieşire

Fişierul arbore1.out va conţine un singur număr reprezentând răspunsul la întrebarea lui Mitruţ, modulo 666013.

Restricţii

1 ≤ N ≤ 100 000
• Pentru 70% din teste N ≤ 2 000
• Rădăcina arborelui este nodul 1
• Pentru 10% din teste N ≤ 7
• Arborele dat nu este neapărat binar (un nod poate avea mai mult de doi fii).

Exemple

arbore1.inarbore1.outExplicaţii
5 1 2 3 1 2 4 2 5 8 Modurile în care putem plasa numerele în nodurile arborelui dat sunt:



autor: Cătălin Perţicaş
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2011: sport2, macheta, butoane, acces, mxl, segmente, tsunami, tort1, ec, ape, poligon4, stalpi2, furnici1, telecab, ikebana, posta, fotbal1, xmoto, radare, pamant, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci, joc18
Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, 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, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
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, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, 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
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor